版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434804
详细代码可以fork下Github上leetcode项目,不定期更新。
题目摘自leetcode:
找第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;
}
比较直观的做法,先排序,把最大的几个元素放在奇数位置,直到放不下。接着把剩余元素也从大到小放入偶数位置。
代码如下:
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。
起初在找它们本身的性质,不难发现一些性质:
一看就知道了当然是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;
}
所以这种排序是利用两个元素之间的关系来排的,而非像之前排序那样,每个元素是独立的。厉害厉害,不知道有什么理论可以证明这种正确性。
字典序,有点像Trie树,如果能够联想到Trie树,可以通过preOrder步进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来求,的确高明。