————————————原题链接 任意给一个数组如[5, 2, 6, 1]，你需要找出数组中每个数的特征，并返回一个特征数组
特征：这个数后面比这个数小的数 的总和，如第一个数字5，在5后面比5还小的数有2，1**两个数**，所以返回数组第一位是2
所以上面样例数组返回为：[2, 1, 1, 0]，见下面具体描述
Given nums = [5, 2, 6, 1]To the right of 5 there are 2 smaller elements (2 and 1).To the right of 2 there is only 1 smaller element (1).To the right of 6 there is 1 smaller element (1).To the right of 1 there is 0 smaller element.以上面样例进行分析[5, 2, 6, 1] 考虑对归并排序归并过程进行处理，归并排序递归树如下： 
先定义一个结构封装数组，这个struct有： 1、数组值 2、索引值 3、计数器【用于储存比它小的数，可以用vector实现】
如图，对归并过程进行处理
在5和2归并时，让5成为左边数组L，让2成为右边数组R 进行归并，5>2，所以将2取出，这个时候将左边数组L的每个数的计数器放入1，然后将5取出，得到归并后数组[2, 5]，5的计数器里有个2
同样6和1归并，归并后数组[1, 6]，6的计数器里有个1
[2, 5] 和 [1, 6] 归并： ①首先取出右边数组R 中的1，将1放入2和5的计数器中 ②取出左边数组L的2，不放入任何计数器 ③取出左边数组L的5，不放入任何计数器 ④取出右边数组R的6，准备放入左边数组L，但L已经没有数了（因为2和5都被取出来了），所以不能放入计数器中
最后归并结果[1, 2, 5, 6]，计数器里数值为 1：计数器里没有值 2：1 5：2，1【首先放入2，再放入1】 6：1
根据上面封装的数据结构里的原始索引下标，对于数组[5, 2, 6, 1] 1–>4 2–>2 5–>1 6–>3
结合索引值和计数器里的数值，我们得到最终返回数组[2, 1, 1, 0]
实现细节：
1、 封装数据结构不需要默认构造函数是因为，下面使用到的new操作符不会使用这个默认构造函数
2、在数据结构里重载“=”操作符的时候，需要将原来的计数器清空来接收新的计数器值【具体见源码】
#include <iostream>#include <vector>using namespace std;/*定义一个struct封装数组array这个struct有：1、数组值 2、下标索引 3、smaller_numbers的计数器【一个vector数组】 */ struct my_array{ int value; int index; vector<int> smaller_numbers; my_array &Operator = (const my_array& b) { value = b.value; index = b.index; int size = b.smaller_numbers.size(); smaller_numbers.clear(); for(int i = 0; i < size; i ++) smaller_numbers.push_back(b.smaller_numbers[i]); return *this; }};vector<int> count_smaller_numbers(my_array* array, int n_size);void merge_sort(my_array* array, int start, int end);void merge(my_array* array, int start, int mid, int end);int main(){ //获取数组 int n_size = 0; cin >> n_size; my_array* array = new my_array[n_size]; for(int i = 0; i < n_size; i ++) { cin >> array[i].value; array[i].index = i; } vector<int> result = count_smaller_numbers(array, n_size); for(int i = 0; i < result.size(); i ++) cout << result[i] << " "; return 0;}vector<int> count_smaller_numbers(my_array* array, int n_size){ merge_sort(array, 0, n_size - 1); //根据struct里的索引值和vector大小创建一个数组存储结果 vector<int> result = vector<int>(n_size, 0);//创建一个大小为 n_size 的 vector 并将其全初始化为 0 for(int i = 0; i < n_size; i ++) result[array[i].index] = array[i].smaller_numbers.size(); return result;}void merge_sort(my_array* array, int start, int end){ if(start < end) { int mid = (start + end) / 2; merge_sort(array, start, mid); merge_sort(array, mid + 1, end); merge(array, start, mid, end); }}void merge(my_array* array, int start, int mid, int end){ /*将左边数组与右边数组归并，原则如下： 只有右边数组归并到结果数组中时，才使剩下的左边数组中的smaller_numbers计数 */ //将其分为左边数组和右边数组，并赋值 int left_size = mid - start + 1; int right_size = end - mid; my_array* left = new my_array[left_size]; my_array* right = new my_array[right_size]; for(int i = 0, k = start; k <= mid; k ++) left[i ++] = array[k]; for(int i = 0, k = mid + 1; k <= end; k ++) right[i ++] = array[k]; //进行归并 int left_count = 0; int right_count = 0; int a_count = start;//记录array数组的起始位置 while(left_count < left_size && right_count < right_size) { if(left[left_count].value > right[right_count].value) { array[a_count ++] = right[right_count]; int select = right[right_count].value; for(int i = left_count; i < left_size; i ++) left[i].smaller_numbers.push_back(select); right_count ++; } else { array[a_count ++] = left[left_count ++]; } } while(left_count < left_size) array[a_count ++] = left[left_count ++]; while(right_count < right_size) array[a_count ++] = right[right_count ++]; delete [] left; delete [] right; }新闻热点
疑难解答
