vlambda博客
学习文章列表

那些可以用快速排序秒杀的经典题

对滴,我们今天先来说一下那个非常经典的荷兰国旗问题。
问题来源:
https://www.jianshu.com/p/356604b8903f
问题描述:
荷兰国旗是由红白蓝3种颜色的条纹拼接而成,如下图所示:
荷兰国旗
假设这样的条纹有多条,且各种颜色的数量不一,并且随机组成了一个新的图形,新的图形可能如下图所示,但是绝非只有这一种情况:
那些可以用快速排序秒杀的经典题
荷兰国旗问题
需求是:把这些条纹按照颜色排好,红色的在上半部分,白色的在中间部分,蓝色的在下半部分,我们把这类问题称作荷兰国旗问题
我们把荷兰国旗问题用数组的形式表达一下是这样的:
给定一个整数数组,给定一个值 K,这个值在原数组中一定存在,要求把数组中小于 K 的元素放到数组的左边,大于K的元素放到数组的右边,等于K的元素放到数组的中间。
这不就是我们之前说过的 三向切分 吗?一模一样!
那么 leetcode 有没有相似问题呢?当然有的,我们一起来看下面这道题
   leetcode 75 颜色分类
题目描述:
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例 1:
输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]
示例 2:
输入:nums = [2,0,1]
输出:[0,1,2]
示例 3:
输入:nums = [0]
输出:[0]
示例 4:
输入:nums = [1]
输出:[1]
解题思路
这个题目我们使用 Arrays.sort() 解决,哈哈,但是那样太无聊啦,题目含义就是让我们将所有的  0 放在前面,2放在后面,1 放在中间, 是不是和我们上面说的荷兰国旗问题一样。此时我们仅仅将 1 做为基准值。
下面我们直接看代码吧,和快速排序优化三向切分代码基本一致。
class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        int left = 0;
        //这里和三向切分不完全一致
        int i = left;
        int right = len-1;

        while (i <= right) {
             if (nums[i] == 2) {
                 swap(nums,i,right--);
             } else if (nums[i] == 0) {
                 swap(nums,i++,left++);
             } else {
                 i++;
             }
        }     
    }
    public void swap (int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
另外我们看这段代码,有什么问题呢?那就是我们即使完全符合时,仍会交换元素,这样会大大降低我们的效率。
例如:[0,0,0,1,1,1,2,2,2]
此时我们完全符合情况,不需要交换元素,但是按照我们上面的代码,0,2 的每个元素会和自己进行交换,所以这里我们可以 根据  i  和 left 的值是否相等来决定是否需要交换 ,大家可以自己写一下。
下面我们看一下另外一种写法
这个题目的关键点就是,当我们 nums[i] 和 nums[right] 交换后,我们的 nums[right] 此时指向的元素是符合要求的,但是我们 nums[i] 指向的元素不一定符合要求,所以我们需要继续判断, nums[i] 是否还需要和 nums[left] 进行交换。
那些可以用快速排序秒杀的经典题
细节地方
我们 2 和 0 交换后,此时 i 指向 0 ,0 应放在头部,所以不符合情况,所以 0 和 1 仍需要交换。下面我们来看一下动画来加深理解吧。

代码

class Solution {
    public void sortColors(int[] nums) {

        int left = 0;
        int len = nums.length;
        int right = len - 1;
        for (int i = 0; i <= right; ++i) {
            if (nums[i] == 0) {             
                swap(nums,i,left);
                left++;
            }
            if (nums[i] == 2) {
                swap(nums,i,right);
                right--;
                //如果不等于 1 则需要继续判断,所以不移动 i 指针,i--
                if (nums[i] != 1) {
                    i--;
                }
            }
        }

    }
    public void swap (int[] nums,int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
好啦,这个问题到这就结束啦,是不是很简单啊。
因为之前咱们小屋进行了迁移,所以各位的星标被自动取消了,为了防止错过小屋的文章推送,大家记得 给小屋加个星标 啊,感谢。拜了个拜,我们下期见!

剑指 Offer 45. 把数组排成最小的数,leetcode 179 最大数

这两个问题根本上也是排序问题,但是我们可能并不知道为什么可以用排序来解决,下面我们来一起扒一下吧!

题目描述

输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"

示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

题目解析

题目很容易理解,就是让我们找出拼接的所有数字中最小的一个,但是我们需要注意的是,因为输出结果较大,

所以我们不能返回 int  应该将数字转换成字符串,所以这类问题还是隐形的大数问题

我们看到这个题目时,可能想到的是这种解题思路,我们首先求出数组中所有数字的全排列,然后将排列拼起来,最后再从中取出最小的值,

但是我们共有 n 个数,则有 n !个排列,显然数目是十分庞大的,那么我们有没有其他更高效的方法呢?

大家先来思考一下这个问题。

我们假设两个数字 m , n 可以拼接成 mn 和 nm 那么我们怎么返回最小的那个数字呢?

我们需要比较 mn 和 nm ,假设 mn < nm 则此时我们求得的最小数字就是  mn

注:mn 代表 m 和 n 进行拼接,例如 m = 10, n = 1,mn = 101

当 mn < nm 时,得到最小数字 mn, 因为在最小数字 mn 中 ,m 排在 n 的前面,我们此时定义 m  "小于"  n。

注意:此时的 "小于" ,并不是数值的 < 。是我们自己定义,因为 m 在最小数字 mn  中位于 n  的前面,所以我们定义 m "小于" n。

下面我们通过一个例子来加深下理解。

假设 m = 10,n = 1 则有 mn =  101 和 nm = 110

我们比较 101 和 110 ,发现 101 < 110 所以此时我们的最小数字为 101 ,又因为在最小数字中 10 (m) 排在 1(n) 的前面,我们根据定义则是 10 “小于” 1。

这时我们自己定义了一种新的,比较两个数字大小的规则,但是我们怎么保证这种规则是有效的?

我们怎么能确保通过这种规则,拼接数组中所有数字(我们之前仅仅是通过两个数字进行举例),得到的数就是最小的数字呢?

我们或许想当然的认为按照上面规则可以得到最小值,并没有经过证明。

下面我们一起来证明一下,我们为什么可以用上面的规则来解决这道题。

下面我们先来证明下规则的有效性

注:为了便于分辨我们用 A,B,C 表示数字, a,b,c 表示数字用十进制表示时的位数

(1)自反性:AA = AA,所以 A 等于 A

(2)对称性:如果 A "小于" B 则 AB < BA,所以 BA > AB 则 B "大于" A

(3)传递性:传递性的证明稍微有点复杂,大家需要仔细阅读。

如果 A“小于” B,则 AB < BA, 假设 A 和 B 用十进制表示时分别有 a 位和 b 位

则 AB = A * 10 ^ b + B ,  BA = B * 10 ^ a + A

例 A = 10, a = 2 (两位数) B = 1, b = 1 (一位数)

AB  = A * 10 ^ b + B = 10 * 10 ^ 1 + 1 = 101

BA  = B * 10 ^ a + A =  1 * 10 ^ 2 + 10 = 110

AB  < BA  则  A * 10 ^ b + B  <   BA = B * 10 ^ a + A  整理得

A / (10^a - 1) < B / (10 ^ b - 1)

同理,如果 B “小于” C 则 BC < CB ,C 用十进制表示时有 c 位,和前面推导过程一样

BC = B * 10 ^ c + C

CB = C * 10 ^ b + B

BC < CB 整理得 B / (10 ^ b - 1) <  C / (10 ^ c - 1);

我们通过

A / (10 ^ a - 1) < B / (10 ^ b - 1) ,B / (10 ^ b - 1) <  C / (10 ^ c - 1);

可以得到

A / (10^a - 1)   < C / (10 ^ c - 1)

则可以得到 AC < CA 即 A “小于” C

传递性证得。

注:可能用手机看证明过程不太舒服,大家可以后台回复 证明,获取清晰明了的手写版证明过程

我们通过上面的证明过程知道了我们定义的规则,满足自反性,对称性,传递性,则说明规则是有效的。

接下来我们证明,利用这种规则得到的数字,的确是最小的。我们利用反证法来进行证明

我们先来回顾一下我们之前定义的规则

当 mn < nm 时,得到最小数字 mn, 因为在最小数字 mn 中 ,m 排在 n 的前面,

我们此时定义 m  "小于"  n。

我们根据上诉规则得到的数字为 xxxxxxxx

假设存在这么一对字符串 A ,B  ,虽然 AB < BA,即 A "小于" B,按照之前的规则,在组成的最小数中,A 应该排在 B 的前面,但是在最小数中 A 排在了 B 的后面。

则共有这么几种情况

见下图

其实我们可以归结为两大类, B 和 A 之间没有其他值, B 和 A 之间有其他值。

我们先来看没有其他值的情况

假设我们求得的最小值为 XXXXBA, 虽然 A "小于" B,但是在最后结果中 B 排在了 A 的前面,这和我们之前定义的规则是冲突的,大家思考一下这个值为最小值吗?

假设 XXXXBA为最小值,但是因为 A "小于" B ,则 AB < BA ,

所以 XXXXAB 一定小于 XXXXBA 。

和我们之前的假设矛盾。

当然 BAXXXX 也一样。

下面我们来看当 B 和 A 之间有其他值的情况

即 BXXXXA

我们可以将 XXXX 看成一个字符串 C,则为 BCA

因为求得的最小值为 BCA ,

在最小值 BCA 中 B 在 C 的前面,C 在 A 的前面,

则 BC < CB, CA < AC,B "小于 C", C “小于” A

根据我们之前证明的传递性

则  B "小于" A

但是我们假设是 A “小于” B ,与假设冲突,证得

综上所述,得出假设不成立,从而得出结论:对于排成的最小数字,不存在满足下述关系的一对字符串:虽然 A "小于" B , 但是在组成的最小数中 B 排在了 A 的前面.

好啦,我们证明了我们定义的规则有效,通过定义的规则可以得到拼接的最小值,下面我们直接看代码吧。继续使用我们的三向切分来解决

class Solution {
    public String minNumber(int[] nums) 
        String[] arr = new String[nums.length];
        //解决大数问题,将数字转换为字符串
        for (int i = 0 ; i < nums.length; ++i) {
            arr[i] = String.valueOf(nums[i]);
        }

        quickSort(arr,0,arr.length-1);
        StringBuffer str = new StringBuffer();

        for (String x : arr) {
            str.append(x);
        }
        return str.toString();
    }
    public void quickSort(String[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int low = left;
        int hight = right;
        int i = low+1;
        String pivot = arr[low];

        while (i <= hight) {
             //字典序
            if ((pivot+arr[i]).compareTo(arr[i]+pivot) > 0 ) {
                 swap(arr,i++,low++);
            } else if ((pivot+arr[i]).compareTo(arr[i]+pivot) < 0) {
                 swap(arr,i,hight--);
            } else {
                 i++;
            }
        }

        quickSort(arr,left,low-1);
        quickSort(arr,hight+1,right);

    }
    public void swap(String[] arr, int i, int j) {
        String temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

大家理解了上面的题目之后,还可以去解决一下 leetcode 179 最大数,思路一致,