排序

一、数据流中的中位数

题目描述：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

解题思路：这里考虑到是从数据流中获取，那么数据就是不断更新的。使用大顶堆来存放排序后前半部分（小的数），使用小顶堆来存放排序后的后半部分（大的数）。其中需要注意的是以下堆的几个操作：

1. 将元素入堆：m.push_back(x);

2. 向堆中添加新的元素作为叶子节点：push_heap(m.begin(),m.end(),less<int>())

3. 堆顶元素出堆：

1. pop_heap(m.begin(),m.end(),less<int>())

2. m.pop_back()

classSolution {
private:vector<int>max;vector<int>min;
public:voidInsert(int num){int size=max.size()+min.size(); //统计整个数据的长度if((size&1)==0) //这里先判断奇偶性，如果是奇数个数字，则遍历大顶堆，统计前半部分数组。{if(max.size()>0&&num<max[0]){max.push_back(num);push_heap(max.begin(),max.end(),less<int>()); //添加数据流中的新元素，作新的叶节点num=max[0]; //获取堆顶元素以便放到后半部分数据组成的小顶堆中pop_heap(max.begin(),max.end(),less<int>()); //堆顶元素出堆max.pop_back();}//将大顶堆中的堆顶元素放到小顶堆中以便平衡元素min.push_back(num);push_heap(min.begin(),min.end(),greater<int>());}else{if(min.size()>0&&num>min[0]){min.push_back(num);push_heap(min.begin(),min.end(),greater<int>()); //添加数据流中的新元素num=min[0]; //获取堆顶元素以便放到前半部分数据组成的大顶堆中pop_heap(min.begin(), min.end(),greater<int>()); //堆顶元素出堆min.pop_back();}//将小顶堆中的堆顶元素放到大顶堆中以便平衡元素max.push_back(num);push_heap(max.begin(), max.end(),less<int>()); //堆顶元素出堆}}doubleGetMedian(){int size=max.size()+min.size();if(size<=0) return0;if((size&1)==0) //判断奇偶性return (max[0]+min[0])/2.0;elsereturn min[0];}};

二、最小的K个数

题目描述：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

解题思路：

• 方法一：使用sort排一遍序，如果没有时间复杂度的要求的话，可以OK没问题。

classSolution {
public:vector<int> GetLeastNumbers_Solution(vector<int> input, int k){vector<int> v;if(k>input.size())return v;sort(input.begin(),input.end());for(int i=0;i<k;i++)v.push_back(input[i]);return v;      }
};

• 方法二：使用快排的思想，通过函数计算，使k以前的数都小于k，k之后的数都大于k，这样，最终只需要取前k个数即可。时间复杂度o(n)。

#include<iostream>#include<vector>usingnamespace std;
inteach_sort(vector<int>&a,int i,int j){int tmp=a[i];if(i<j){while(i<j&&a[j]>tmp) j--;if(i<j) a[i]=a[j];while(i<j&&a[i]<tmp) i++;if(i<j) a[j]=a[i];}a[i]=tmp;return i;
}
voidkp_sort(vector<int>&Array,int Begin,int End){if(Begin<End){int tmp=each_sort(Array,Begin,End); //查找每次分配完成的中点kp_sort(Array,Begin,tmp-1); //左边kp_sort(Array,tmp+1,End); //右边}
}
intmain(){vector<int>arr{1,3,2,4,6,5,7,9,13,12};int k;cin>>k;kp_sort(arr,0,arr.size()-1);for(int j=0;j<k;j++)cout<<arr[j]<<',';return0;
}

快排java实现：

classSolution {publicint[] getLeastNumbers(int[] arr, int k) {randomizedSelected(arr, 0, arr.length - 1, k);int[] vec = newint[k];for (inti=0; i < k; ++i) {vec[i] = arr[i];}return vec;}privatevoidrandomizedSelected(int[] arr, int l, int r, int k) {if (l >= r) {return;}intpos= randomizedPartition(arr, l, r);intnum= pos - l + 1;if (k == num) {return;} elseif (k < num) {randomizedSelected(arr, l, pos - 1, k);} else {randomizedSelected(arr, pos + 1, r, k - num);}}// 基于随机的划分privateintrandomizedPartition(int[] nums, int l, int r) {inti=newRandom().nextInt(r - l + 1) + l;swap(nums, r, i);return partition(nums, l, r);}privateintpartition(int[] nums, int l, int r) {intpivot= nums[r];inti= l - 1;for (intj= l; j <= r - 1; ++j) {if (nums[j] <= pivot) {i = i + 1;swap(nums, i, j);}}swap(nums, i + 1, r);return i + 1;}privatevoidswap(int[] nums, int i, int j) {inttemp= nums[i];nums[i] = nums[j];nums[j] = temp;}
}

三、剑指 Offer II 032. 有效的变位词

思路：排序

classSolution {publicbooleanisAnagram(String s, String t) {if(s.length()!=t.length()||s.equals(t)){returnfalse;}char[] a=s.toCharArray();char[] b=t.toCharArray();Arrays.sort(a);Arrays.sort(b);return Arrays.equals(a,b);}
}