算法细节系列（35）：不一样的排序
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434804
算法细节系列（35）：不一样的排序
详细代码可以fork下Github上leetcode项目，不定期更新。
题目摘自leetcode：
- Leetcode 215. Kth Largest Element in an Array
- Leetcode 324. Wiggle Sort II
- Leetcode 179. Largest Number
- Leetcode 440. K-th Smallest in Lexicographical Order
Leetcode 215. Kth Largest Element in an Array
找第k大有点类似于找中位数，时间复杂度为何能达到O(n)O(n)？
答：因为比k小的元素和比k大的元素不需要维护有序性，和中位数一个道理。
所以自然我们能够想到一种【迭代分治】的做法，用快速排序的partition思想，之所以快的原因在于找第k大元素时，可以排除一部分的查找时间。
nums = {5,1,3,2,4,9,6,7,8};
找第一大的元素（9）怎么找？
切分:
{1,3,2,4} 5 {9,6,7,8}
切分完毕后，有个很好的性质，直接排除左半部分的元素，所以我们可以用类似二分查找的结构来实现快速寻找，其实就是一个递归。快的原因在于排除了部分不需要比较的元素，把问题归为降为原来的一半，而之所以可以这么做是因为我们只要第k大，而第k大的性质：
比它小的元素有n-k个，比它大的元素有k-1个罢了。
代码如下：
public int findKthLargest(int[] nums, int k) {
k = nums.length - k;
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
final int j = partition(nums, lo, hi);
if(j < k) {
lo = j + 1;
} else if (j > k) {
hi = j - 1;
} else {
break;
}
}
return nums[k];
}
private int partition(int[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
while(true) {
while(i < hi && a[++i] < a[lo]);
while(j > lo && a[--j] > a[lo]);
if(i >= j) {
break;
}
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
private void exch(int[] a, int i, int j) {
final int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}Leetcode 324. Wiggle Sort II
比较直观的做法，先排序，把最大的几个元素放在奇数位置，直到放不下。接着把剩余元素也从大到小放入偶数位置。
代码如下：
public void wiggleSort(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int[] aux = new int[n];
for (int i = ((n - 1) % 2 == 0 ? n - 1 : n - 2), k = 0; i >= 0; i -= 2){
aux[i] = nums[k++];
}
for (int i = 1, k = n - 1; i < n; i += 2){
aux[i] = nums[k--];
}
for (int i = 0; i < n; i++){
nums[i] = aux[i];
}
}时间复杂度为O(nlogn)O(n \log n)，且空间复杂度为O(n)O(n)，借着上题的思路，只需要找到整个数组的中位数即可，大于中位数的num放入奇数位，而小于中位数的放入偶数位即可。时间复杂度可以降到O(n)O(n)，但问题来了，该怎么把空间复杂度降到O(1)O(1)呢？
答案是虚拟坐标映射，映射函数如下：
private int map(int i, int n){
return (1 + 2 * i) % (n | 1);
}
n | 1其实是一种结合判断条件和赋值于一身的代码小技巧，实际含义：
if n % 2 == 0; n = n + 1;
if n % 2 != 0; n = n;
map映射的效果是：
n为偶数的情况：
origin : 0 1 2 3 4 5 6 7 8 9
new : 1 3 5 7 9 2 4 6 8 10
n为奇数的情况：
origin : 0 1 2 3 4 5 6 7 8
new : 1 3 5 7 2 4 6 8 10所以我们实际遍历的顺序是new所展示的那样，那么现在有了median这个值，就可比较median的大小来决定是否进行交换。
num与中位数相等怎么办？很有趣，因为在放入奇数坑和偶数坑是交错开来的，所以遇到中位数的情况放在原位置就好了，而不会出现两中位数在一块的情况。
代码如下：
public void wiggleSort(int[] nums) {
int n = nums.length;
int median = findKthLargest(nums, (nums.length + 1) / 2);
int i = 0, lf = 0, rt = n - 1;
while (i <= rt){
if (nums[map(i,n)] > median){
exch(nums, map(lf++, n), map(i++,n));
}
else if (nums[map(i, n)] < median){
exch(nums, map(rt--, n), map(i, n));
}
else{
i++;
}
}
}
private int map(int i, int n){
return (1 + 2 * i) % (n | 1);
}
public int findKthLargest(int[] nums, int k) {
k = nums.length - k;
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
final int j = partition(nums, lo, hi);
if(j < k) {
lo = j + 1;
} else if (j > k) {
hi = j - 1;
} else {
break;
}
}
return nums[k];
}
private int partition(int[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
while(true) {
while(i < hi && a[++i] < a[lo]);
while(j > lo && a[--j] > a[lo]);
if(i >= j) {
break;
}
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
private void exch(int[] a, int i, int j) {
final int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}注意：while中的终止条件怎么看？看i自增的情况和rt自减，因为它们分别属于三种不同情况，每种情况中都不可能出现同时i++和rt–，所以终止条件自然是i <= rt，而不是i < rt。
Leetcode 179. Largest Number
起初在找它们本身的性质，不难发现一些性质：
- 长度相同的number，先选number大的。 如：123，321，选择 321123，而不是123321
- 长度不同的number该如何决策？ 如：830，8301，选择 8308301 还是 8301830？
一看就知道了当然是8308301咯，没错，现在有两种做法，第一种是找到这种选择的模式，编写算法，但实际情况很难做到。第二种，把判断830在8301的前面还是后面，交给计算机来完成。其实只要把两种情况列出来，判断一下大小自然就能知道谁在谁前面了。
接着神奇的事情发生了，也是我第一次接触这样的排序比较，实在高明，对于第一种情况和第二种情况是完全可以合并的，假定给了两个number：
String a1 = num1 + num2;
String s2 = num2 + num1;
如何决定它们的顺序？对新生成的a1和a2来一次比较，
谁大就把num1放在前面，num2放在后面。所以其实是一种特殊的排序。。。对comparator做点操作就好了。。。
代码如下：
public String largestNumber(int[] nums) {
String[] s = new String[nums.length];
for (int i = 0; i < nums.length; ++i){
s[i] = nums[i] + "";
}
Arrays.sort(s, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
String s1 = o1 + o2;
String s2 = o2 + o1;
return s1.compareTo(s2);
}
});
if (s[s.length - 1].charAt(0) == '0' ) return "0";
String ans = "";
for (String n : s){
ans = n + ans;
}
return ans;
}所以这种排序是利用两个元素之间的关系来排的，而非像之前排序那样，每个元素是独立的。厉害厉害，不知道有什么理论可以证明这种正确性。
Leetcode 440. K-th Smallest in Lexicographical Order
字典序，有点像Trie树，如果能够联想到Trie树，可以通过preOrder步进k步，得到的结点必然是所求的结果。
两个操作：
- 访问子结点， cur = cur * 10；
- 访问相邻结点，cur = cur + 1；
看图：
何时访问子结点？何时访问邻居结点？
- 计算到相邻结点的步数，如果步数小于剩余k的能够行走的步数，访问子结点。
- 否则，访问邻居结点。
所以这个问题转换为求相邻结点所需要的步数是多少？
private int calStep(int n, long n1, long n2){
int step = 0;
while (n1 <= n){
step += Math.min(n + 1, n2) - n1;
n1 *= 10;
n2 *= 10;
}
return step;
}迭代求解每一层的结点数，如第三层n2= 200, n1 = 100，得n2 - n1 = 100，当然这是n超过n2的情况。如果n小于n2，则说明没有那么多实际的结点，直接计算从n到该层的结点即可。
整体代码如下：
public int findKthNumber(int n, int k) {
int cur = 1;
k = k - 1;
while (k > 0){
int steps = calStep(n, cur, cur + 1);
if (steps <= k){
cur = cur + 1;
k -= steps;
}
else{
cur *= 10;
k -= 1;
}
}
return cur;
}
private int calStep(int n, long n1, long n2){
int step = 0;
while (n1 <= n){
step += Math.min(n + 1, n2) - n1;
n1 *= 10;
n2 *= 10;
}
return step;
}相邻结点的步数求解慢慢磨就能出来了，但这道题主要是字典序的访问子结点可以用 cur *=10 来代替，转换成了树的preOrder来求，的确高明。