对数组排序时间复杂度要求O(n)与找中位数不能用排序

对数组排序时间复杂度要求O(n)

思路

  首先我们常规的排序都不能使用。所以我先遍历了一边数组，找到最小值和最大值。然后以它们的差值动态开辟了一段区间作为闭散列。然后再遍历了一边数组把相应元素的出现次数映射到了闭散列中。最后遍历一边闭散列表，把大于0的元素按其下标和保存的次数，重新赋值给原数组，得此完成排序。

代码

void sort(int *arr, size_t length) { int min=arr[0]; int max=arr[0]; size_t idx = 0; while (idx < length) { if (min>arr[idx]) min = arr[idx]; if (max < arr[idx])max = arr[idx]; ++idx; } int * sort_buf = new int[max-min+1]; memset(sort_buf, 0, (max - min + 1)*sizeof(int)); idx = 0; while (idx < length) { ++sort_buf[arr[idx++] - min]; } for (int i = 0, j = 0; j < max - min + 1&&i<length; j++) { while (sort_buf[j] != 0) { arr[i++] = j+min; --sort_buf[j]; } } delete sort_buf; }

找中位数不能用排序

思路

  我使用的是快排的思想。根据快排中的思想，进行一次快排处理，基准值左边区间比基准值小，右边区间比基准值大。只要我们保证中位数对应的下标pos一直在我们快排处理的区间中即可。就这样不断递归，使之区间只有一个元素就结束，这样就能找到中位数了。如果原数组大小是偶数则有2个中位数，那我们还需在递归处理完后，可以找到length/2这个中位数并且可以确定前面区间元素比length/2后面的元素都小，那么第二个中位数，就是前面区间的最大数。

int pation(int*arr, int left, int right) { int begin = left; int end = right; int key = arr[right]; while (begin < end) { while (begin < end&&arr[begin] <= key) ++begin; arr[end--] = arr[begin]; while (begin < end&&arr[end] >= key) --end; if (begin < end) arr[begin++] = arr[end]; } arr[begin] = key; return begin; } void _Find_mid(int*arr, int left, int right,int pos) { if (left < right) { int Base = pation(arr, left, right); if (Base == pos)return; else if (Base>pos) { if (Base == right)Base = right - 1; //防止Base==right 或者 Base==left的死循环 _Find_mid(arr, left, Base, pos); } else{ if (Base == left)Base = left - 1; _Find_mid(arr, Base, right, pos); } } } pair<int,int> Find_mid(int*arr, size_t length) { _Find_mid(arr, 0, length - 1,length/2); int first_mid = arr[0]; if (length % 2 == 0) { for (size_t idx = 0; idx < length / 2; ++idx) { if (first_mid < arr[idx]) first_mid = arr[idx]; } return pair<int, int>(first_mid, arr[length / 2]); } else{ return pair<int, int>(arr[length / 2], 0); } }