专栏首页机器学习入门算法细节系列(35):不一样的排序

算法细节系列(35):不一样的排序

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/73251784

算法细节系列(35):不一样的排序

详细代码可以fork下Github上leetcode项目,不定期更新。

题目摘自leetcode:

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来求,的确高明。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 挑战程序竞赛系列(81):4.3 LCA(1)

    挑战程序竞赛系列(81):4.3 LCA(1) 传送门:POJ 2763: Housewife Wind 题意: XX村里有n个小屋,小屋之间有双向可达的道...

    用户1147447
  • 挑战程序竞赛系列(32):4.5 A*与IDA*

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 挑战程序竞赛系列(36):3.3线段树和平方分割

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • P1828 香甜的黄油 Sweet Butter

    题目描述 农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜...

    attack
  • 51Nod-1203-JZPLCM

    ACM模版 描述 ? 题解 这个题的解法好像好多好多,可以线段树解,自然也可以用树状数组解,还有大佬直接莫队推过,我这里用的树状数组搞得。 首先将数进行拆解,拆...

    f_zyj
  • 1751:分解因数

    1751:分解因数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述给出一个正整数a,要求分解成若干个正整数的乘积,即a = ...

    attack
  • 挑战程序竞赛系列(81):4.3 LCA(1)

    挑战程序竞赛系列(81):4.3 LCA(1) 传送门:POJ 2763: Housewife Wind 题意: XX村里有n个小屋,小屋之间有双向可达的道...

    用户1147447
  • 口算训练 HDU - 6287

    小Q非常喜欢数学,但是他的口算能力非常弱。因此他找到了小T,给了小T一个长度为n的正整数序列a1,a2,…,an,要求小T抛出m个问题以训练他的口算能力。

    用户7727433
  • 原 初学算法-快速排序与线性时间选择(De

    不高不富不帅的陈政_
  • 计算机二级大题.

    1题 #include <iostream> using namespace std; class MyClass { public: MyClass(...

    东风冷雪

扫码关注云+社区

领取腾讯云代金券