天道酬勤,学无止境

LeetCode 75.颜色分类(荷兰国旗问题)

题目:

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、1 和 2 分别表示红色、白色和蓝色

思路:

  1. 本题是典型的荷兰国旗问题,我们不能仅仅局限于当前题目,有的题目变一下就不是三个数,而是三个区域,小于num的,等于num的以及大于num的。
  2. 为了规划区域,我们可以设置两个指针left,rightleft表示左边区域的右边界,初始时指向第一个元素的前一个,索引为-1right表示右边区域的左边界,初始时指向最后一个元素的后一个,索引为nums.length,指针cur表示当前遍历的值,这样就会出现三种情况,我们假定num为目标分界值
    1. 当前值nums[cur]<num,那么当前值就是属于left区域的,让该值和left的下一位交换,然后让left++,cur++,这样就保证该值被包进了left区域
    2. 当前值nums[cur]==num,那么当前值就是中间区域的,只需要让cur++
    3. 当前值nums[cur]>num,那么当前值就是属于right区域的,我们让当前值和right区域的前一个进行交换,然后让right--,这样就保证了该值被包进了right区域注意,这个情况下指针cur不能+1,因为cur和right区域前一个值交换之后的当前值是从后边来的,还没有遍历过,所以不能记着将cur++
  3. 最后当遍历到cur指针和right指针相碰时,说明所有元素遍历完毕,整个数组也就有序了。

以下为代码+注释:

    public void sortColors(int[] nums) {
        int cur = 0;
        // 初始化时左边区域指向第一个元素的前面,
        // 右边区域指向最后一个元素的后面,两个指针都是一直在向中间扩张
        int left = -1, right = nums.length;
        // 从第一个开始遍历,直到当前遍历的值和右边的区域重合
        while(cur != right){
            // 情况一:如果当前值小于1,将nums[cur]和left区域的下一个做交换,让后让left区域向右扩一个,最后cur++
            if(nums[cur] < 1){
                int temp = nums[cur];
                nums[cur] = nums[left + 1];
                nums[left + 1] = temp;
                left++;
                cur++;       
            }else if(nums[cur] == 1){
                // 情况二:如果当前值等于1,cur++,其他什么也不干
                cur++;
            }else{
                // 情况三:如果当前值大于1,将当前值和right区域的前一个做交换,right区域向左扩,注意此情况cur指针不动,因为交换过之后当前cur指向的值是后面的right区域交换过来的,我们还没有处理过。
                int temp = nums[cur];
                nums[cur] = nums[right - 1];
                nums[right - 1] = temp;
                right--;
            }
        }
    }

笔者也在不断学习,如有错误,欢迎指正!

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐
  • 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] 题解 数轴上,起始位置 i=0,j=0,k=n-1,三数排序要保证的是[0,j-1] 区间内的数是0,[j,i-1] 区间是1,[k,n-1] 区间是2。排序的过程如下: 如果nums[i]==0,就需要就将 i 指针所指向的数与 j 指针所指向的数交换,且由于交换过去了,j 已经是满足等于0的位置了,因此j++,i++如果nums[i]==1,那么i++即可,要满足[j,i-1] 区间,因此i++如果nums[i]==2,需要将2位置交换到k后面,因此k–,i 没有变化是因为交换过去的数字不确定是1还是0。 class Solution { public: void sortColors(vector<int>& nums) { for(int i=0,j=0,k=nums.size()-1;i<=k;) {
  • leetcode75.颜色分类
    题目: 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 示例: 输入:nums = [2,0,2,1,1,0] 输出:[0,0,1,1,2,2] 思路: 第一种方法就是上来就调用排序函数,就可以了。 第二种方法是先对数组遍历,分别对三种颜色计数,然后再遍历一遍数组,按照前面计的数修改数组实现顺序排列。 第三种方法 叫做荷兰国旗问题红白蓝,设置两个挡板,左边挡0,这个挡板就是这个左指针前面都是0,右边挡2,就是这个右指针的后边都是2,从左到右遍历这个数组,当是0的时候,交换到左挡板的下一个位置,并且左挡板向右移动一位,然后遍历下一个位置,当是1的时候不用管,接着往下遍历,当是2的时候,放到右挡板的前一位,然后右挡板向前移动一位。 这里可以认为左挡板就在左挡板指针前面那个空里,右挡板就在右挡板指针后面的那个空里,有符合条件的直接交换即可。 注意两个点: 1.边界条件,跳出循环的条件是遍历数组的指针大于右挡板的时候,因为这个时候后面全是2了,都已经交换过来了,不用再遍历了。 2.为啥在这个数等于0的时候,交换到前面以后,左挡板向右移动一位,然后当前遍历数组的指针直接就加1了,但是这个数等于2的时候,交换过来,右挡板向前移动一位
  • 颜色分类
    题目介绍 力扣75题:https://leetcode-cn.com/problems/sort-colors/ 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 分析 本题是经典的“荷兰国旗问题”,由计算机科学家 Edsger W. Dijkstra 首先提出。荷兰国旗是由红白蓝3种颜色的条纹拼接而成,如下图所示: 假设这样的条纹有多条,且各种颜色的数量不一,并且随机组成了一个新的图形,新的图形可能如下图所示,但是绝非只有这一种情况: 需求是:把这些条纹按照颜色排好,红色的在上半部分,白色的在中间部分,蓝色的在下半部分,我们把这类问题称作荷兰国旗问题。本题其实就是荷兰国旗问题的数学描述,它在本质上,其实就是就是一个有重复元素的排序问题。所以可以用排序算法来解决。当然,最简单的方式,就是直接调Java已经内置的排序方法: public void sortColors(int[] nums) { Arrays.sort(nums); } 时间复杂度为O(nlogn)。但显然这不是我们想要的,本题用到的排序算法应该自己实现,而且要根据本题的具体情况进行优化。 方法一:基于选择排序 如果用选择排序的思路,我们可以通过遍历数组,找到当前最小
  • 75. 颜色分类
    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] 提示: n == nums.length1 <= n <= 300nums[i] 为 0、1 或 2 进阶: 你可以不使用代码库中的排序函数来解决这道题吗?你能想出一个仅使用常数空间的一趟扫描算法吗? 解答: class Solution { //荷兰国旗问题 //时间复杂度O(N)。空间复杂度O(1) public void sortColors(int[] nums) { int n0 = 0, n1 = 0; for(int i = 0; i < nums.length; i++){ int num = nums[i]; nums[i] = 2; if(num < 2){ nums[n1++] = 1; } if(num < 1){ nums[n0++] = 0; } } }
  • leetcode刷题笔记75---颜色分类
    题目要求: 算法分析: 本题是荷兰国旗问题。 我的思路最开始也是双指针,只不过是比较指针所指向值的大小再进行变化。即循环判断条件为nums[i]和nums[j]的大小再做出相应的判断,但是这种方法在测试的过程中[2,0,1]这个数组没有通过,而且要求判断的条件为nums[i]==nums[j]时还需要附加判断条件:值为0,1还是2.较为繁琐,由于条件的控制不能完全涵盖每一种情况因此不能采用这种比较指针所指向值的大小再进行变化。 ———————————————————————————————————— 在变换思路之后,依旧使用双指针(也可以理解为三指针),指向不再用来比较大小,而是用作边界,此时的双指针分别是: low:指向0所在的右边界,不包含边界; high:指向2所在的左边界,不包含边界; i:作为索引,指向的数据和0,1,2比较。 这样我们可以进行如下判断和分区: 当nums[i]==0时,和nums[low]交换 当nums[i]==2时,和nums[high]交换 当nums[i]==1时,只需将i做增量。 这种方法还需注意结束条件,不是low与high作比较,而应该是i与high作比较,因为low永远是0的右边界(开)而high永远是2的左边界(开)。 是否有等于号也不是固定的,在于high作为左边界的开or闭。如果编码时设置为开则需要等于号,即在nums[i
  • 经典的“荷兰旗”问题
    1、题目描述:(题目地址:LeetCode75 颜色分类): 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 2、解题思路和Java代码: 这是一个经典的“荷兰旗”问题,由计算机科学家 Edsger W. Dijkstra 首先提出。欧洲很多国家的国旗都是三种颜色的不同分布、排列。 方法一:单指针 我们可以考虑对数组进行两次遍历。在第一次遍历中,我们将数组中所有的 0 交换到数组的头部。在第二次遍历中,我们将数组中所有的 1 交换到头部的 0 之后。此时,所有的 2 都出现在数组的尾部,这样我们就完成了排序。 class Solution { public void sortColors(int[] nums) { int n = nums.length; int ptr = 0; for (int i = 0; i < n; ++i) { if (nums[i] == 0) { int temp = nums[i]; nums[i] = nums[ptr]; nums[ptr] = temp; ++ptr; } } for (int i = ptr; i < n; ++i) { if (nums[i] == 1) { int
  • 排序算法的应用-leetcode
    排序算法的应用 2020.01.06 add桶排序应用 文章目录 排序算法的应用荷兰国旗问题-leetcode-75-颜色分类leetcode-56-合并区间对链表进行插入排序-leetcode-147leetcode-220-存在重复元素 III 荷兰国旗问题-leetcode-75-颜色分类 references: 颜色分类 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 这道题有意思的点在于:区别于普通排序算法,这个题只有三种0 1 2数字,因此常规的排序算法可以使用,但是借助于移动指针,我们也能找到一种时间复杂度为O(N)的算法 const sortColors1=nums=>{ // 对于所有idx<p0 nums[idx]=0,0的右边界p0 // 对于所有的idx>p2 nums[idx]=2,2的左边界p2 let p0=0,curr=0,p2=nums.length-1; while(curr<=p2){ if(nums[curr]===0){ // 交换p0 curr 然后分别右移指针 let temp=nums[p0]; nums[p0]
  • <排序>算法笔记(LeetCode75.颜色分类,88.合并两个有序数组)
    文章目录 一、排序算法原理及实现1.冒泡排序2.选择排序3.插入排序4.希尔排序5.归并排序6.快速排序7.堆排序8.三向切分快速排序 二、排序算法的比较(复杂度与稳定性分析)三、LeetCode题目1.合并两个有序数组2.颜色分类(荷兰国旗问题) 第一次面试,面试问了很多问题都不会,其实那些问题我都有看过,都是一些经典问题,那为什么答不出来呢?因为我只是看过,没有深入理解,没有把它们变成我脑子里的东西。要做到高效率理解所有的要点,就要系统学习。碎片化学习虽然时间耗时少,但打的根基不扎实。 面试具体问了快速排序,尴尬的是快速排序我基本都忘了,回顾那时候,就用了半天看那些排序算法,照着别人的代码敲了一遍,这怎么能掌握呢? 这里有个有趣的可视化视频,戴上耳机: 排序可视化 排序原理和示意图是引用别人的,代码是我自己写的,我感觉我的代码还是挺好理解的。平常搜索,看到别人的代码变量命名和代码风格改来改去,不习惯,不如自己写一遍,巩固下对各种排序算法的理解。 一、排序算法原理及实现 1.冒泡排序 比较相邻的元素。如果前一个元素比后一个元素大,就交换这两个元素的位置。对每一对相邻元素做同样的工作,从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。 public void bubbleSort(int[] nums) { for (int i = 0; i < nums
  • 荷兰旗问题、三分法、Three-Way-Partition 详解
    Three-Way-Partition 荷兰国旗是由红白蓝3种颜色的条纹拼接而成,如下图所示: 假设这样的条纹有多条,且各种颜色的数量不一,并且随机组成了一个新的图形,新的图形可能如下图所示,但是绝非只有这一种情况: 需求是:把这些条纹按照颜色排好,红色的在上半部分,白色的在中间部分,蓝色的在下半部分,我们把这类问题称作荷兰国旗问题。 我们把荷兰国旗问题用数组的形式表达一下是这样的: 给定一个整数数组,给定一个值 Key,这个值在原数组中一定存在,要求把数组中小于 Key 的元素放到数组的左边,大于 Key 的元素放到数组的右边,等于 Key 的元素放到数组的中间,最终返回一个整数数组,其中只有两个值,分别是等于 Key 的数组部分的左右两个下标值。 思考 对于如下数组,我们如何在 O ( n ) O(n) O(n) 的时间完成三分法? 假设对于数组 a a a , 红色区域: a [ 0 ] , a [ 1 ] , . . , a [ l e s s ] a[0],a[1],..,a[less] a[0],a[1],..,a[less] 为小于 k e y key key 的部分 白色区域: a [ l e s s + 1 ] , a [ l e s s + 2 ] , . . , a [ m o r e − 1 ] a[less+1],a[less+2],..,a[more-1
  • LeetCode刷题笔记 75
    题目:颜色分类 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意: 不能使用代码库中的排序函数来解决这道题。 示例: 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶: 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗? 答案: 1.迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。但是需要遍历两次数组。 class Solution { public void sortColors(int[] nums) { int colorCount[] = new int[3]; int j = 0; for(int i = 0; i < nums.length; i++) { if(nums[i] == 0) colorCount[0]++; else if(nums[i] == 1) colorCount[1]++; else if(nums[i] == 2) colorCount[2]++; } for(int i = 0; i < 3; i++)
  • 四种颜色的荷兰国旗算法(Dutch national flag algorithm with four colors)
    问题 我经历了两种和三种颜色的解决方案,但我无法获得四种颜色的解决方案。 请帮忙。 会是rrbb????yyyggg吗rrbb????yyyggg ? 我们将如何交换绿旗? 我尝试了下面的解决方案,但它不能用绿色交换最后一个黄色。 public class count123 { // Java program to sort an array of 0, 1 and 2,3 static void sort0123(int a[], int arr_size) { int lo = 0; int hi = arr_size - 1; int mid = 0,temp=0; int h2=arr_size - 1; while (mid <= hi) { switch (a[mid]) { case 0: { temp = a[lo]; a[lo] = a[mid]; a[mid] = temp; lo++; mid++; break; } case 1: mid++; break; case 2: { temp = a[mid]; a[mid] = a[hi]; a[hi] = temp; hi--; h2=hi; break; } case 3:{ temp = a[mid]; a[mid] = a[h2]; a[h2] = temp; // h2--; //hi=h2
  • LeetCode+剑指offer 题目(按标签汇总)
    前言 所用语言:c++ 。题号用 “剑指XX” 表示的都是剑指上的题,其余都是LeetCode上的题。 计划刷题,3遍以上。 其中,剑指除1题、2题之外,其余全部完整(共66道,3~68)。 2020.02.15 一刷; 2020.04.05 二刷。 该LeedCode笔记参照了下面优秀的博主笔记,并按照他们整理的高频题目来刷的,在此感谢。 博主笔记链接: https://blog.csdn.net/kk55guang2/article/details/85223256 https://www.cnblogs.com/grandyang/p/4606334.html 页面跳转的方法(即,点击题目可跳转到相应题目解答): [点击跳转](https://blog.csdn.net/weixin_43330388/article/details/104331278/#jump) [开始跳](#jump) 文章内容... <span id="jump">跳到这</span> 数组相关(剑指11道) (1)LC 01.两数之和 (2)LC 167 两数之和||-输入有序数组 (3)LC 15.三数之和 (4)LC 16.最接近的三数之和 (5)LC 18.四数之和 (6)LC 217.存在重复元素 (7)LC 26. 删除排序数组中的重复项 (8)LC 80. 删除排序数组中的重复项 II
  • LeetCode刷题算法总结(持续更新)
    1. 指针法 11. 盛最多水的容器(双指针法)15. 三数之和(指针法)16. 最接近的三数之和(指针法)18. 四数之和(双指针) 2. 动态规划 10. 正则表达式匹配(动态规划)5. 最长回文子串(动态规划)32. 最长有效括号(动态规划)44. 通配符匹配(动态规划)72. 编辑距离(动态规划) 3. 贪心 45. 跳跃游戏 II(贪心算法)53. 最大子序和(贪心)55. 跳跃游戏(贪心) 4. KMP应用 28. 实现 strStr()(KMP应用) 5. 滑动窗口 30. 串联所有单词的子串(窗口滑动)76. 最小覆盖子串(滑动窗口) 6. 有限状态机 65. 有效数字(有限状态机) 7. 荷兰旗问题 75. 颜色分类(荷兰旗问题) 8. 单调栈 84. 柱状图中最大的矩形(单调栈) 来源:https://blog.csdn.net/qq_40941722/article/details/108939255
  • 毛里求斯国旗问题(Mauritus national flag problem)
    问题 我已经为荷兰国旗问题做出了解决方案。 但这一次,我想尝试一些更困难的事情:毛里求斯国旗问题 - 4 种颜色,而不是 3 种颜色。对有效算法有什么建议吗? 基本上,毛里求斯国旗问题侧重于如何根据毛里求斯国旗中的颜色顺序(红色、蓝色、黄色、绿色)对给定的配对列表进行排序。 并且数字也必须按升序排序。 方案编程示例输入: ( (R . 3) (G . 6) (Y . 1) (B . 2) (Y . 7) (G . 3) (R . 1) (B . 8) ) 输出: ( (R . 1) (R . 3) (B . 2) (B . 8) (Y . 1) (Y . 7) (G . 3) (G . 6) ) 回答1 这是我想出的。 我使用的是数字而不是颜色。 // l - index at which 0 should be inserted. // m1 - index at which 1 should be inserted. // m2 - index at which 2 should be inserted. // h - index at which 3 should be inserted. l=m1=m2=0; h=arr.length-1 while(m2 <= h) { if (arr[m2] == 0) { swap(arr, m2, l); l++; // m1
  • QuickSort Dijkstra 3 向分区:为什么要进行额外的交换?(QuickSort Dijkstra 3-Way Partitioning: why the extra swapping?)
    问题 给定这里的算法,看看 i 在“X”的场景,会发生以下情况: 场景: i -> "X", "X" > "P" 1. swap("X", "Z"), gt--; // the value at i is now "Z", which is still > "P" 2. swap("Z", "Y"), gt--; // the value at i is now "Y", which is still > "P" 3. swap("Y", "C"), gt--; // Now we finally get a value at i "C" which is < "P" // Now we can swap values at i and lt, and increrement them 4. swap("P", "C"), i++, lt++; 为什么我们不只是递减 gt 直到 gt 指向一个 < lt 处的值(在本例中为“P”),然后我们将该值与 i 处的值交换。 这将节省交换操作。 因此,如果我们针对上述场景执行此操作,我们将执行以下操作: 1. gt-- 2. gt-- 3. swap("X", "C"), gt--; // Now we can swap values at i and lt, and increrement them 4. swap("P", "C")
  • leetcode刷题分类及API
    一、题目分类 加粗表示又做了一遍 1.数组 1)leetcode1 两数之和 2)leetcode11 盛最多的水的容器 3)leetcode15 三数之和 4)下一个排列 5)48. 旋转图像 6)49. 字母异位词分组 7)跳跃游戏 8)56. 合并区间 9)两数之和2 输入有序数组 10)多数元素 11)除自身以外数组的乘积 12) 搜索二维矩阵 13)移动0 14)前K个高频元素 15)找到所有数组中消失的数字 16)和为K的子数组 17)最短无序连续子数组 18)任务调度器 19)每日温度 20)消失的数字 21)猿辅导2020校招3 16 22)面试题 旋转数组 这记不住技巧恐怕不能原地进行吧 23) 搜索二维矩阵 从左下角或右上角开始搜索 2.链表 1)leetcode2 两数相加 2)合并两个有序链表 3)排序链表 4)相交链表 5) 反转链表 6)反转链表 3.字符串 1)leetcode3 无重复的最长子串 2)leetcode5 最长回文子串 3)leetcode10 正则表达式匹配 4)字符串解码 5)回文子串 4. 回溯 1)电话号码的字母组合 2)括号生成 3) 39. 组合总和 4)46. 全排列 5)N皇后问题 6)岛屿数量 6) 组合 7)子集 8) 单词搜索 9) 猿辅导20201 12题 带记忆的回溯,回溯的递归算法要带返回值,不然是有问题的
  • 荷兰国旗问题
    一、问题描述 荷兰国旗问题,顾名思义,就是按照荷兰国旗的形式,给定一个数 x ,将 < x 的数放到左边,=x 的数放中间,>x 的数放右边,将数组中的元素分成三块,有的时候可能要求 <= x 的放左边: 二、解题思路 首先,数组是无序的,如果要求 <= x 放左边,>x 的放右边,将数组分成两部分,该如何做? 我们应当在数组的左边设定一个指针,指针位置以左,代表 <=x 的区域,然后再设计一个指针代表当前数 ,如果当前数 <=x,当前数与 <= 区的下一个数做交换,然后<=区向右扩,当前数右移;如果当前数 >x,那么当前数直接跳下一个。 如果要求 <x 放左,=x 放中间,>x 放右,将数组分成三部分,该如何做? 按照上面的思路,分别在数组两侧设置一个<x区和>x区,再设计一个指针代表当前数,从 0 位置开始右移,如果当前数 <x ,当前数与<区下一个数交换,<区右扩,当前数右移;如果当前数=x,当前数直接跳下一个;如果当前数>x,当前数与>区前一个数交换,>区左移,当前指针不动,因为刚刚从右边交换过来的数还需要再比较一次。这样重复上面的步骤,如果当前指针与>区位置重合,那么停止操作。 三、完整代码 以分成三部分的题目为例,完整代码如下: public static int[] netherlandsFlag(int[] arr, int L, int R, int target
  • 了解荷兰国旗计划(Understanding Dutch National flag Program)
    问题 我正在阅读荷兰国旗问题,但无法理解 C++ 实现中的threeWayPartition函数中的low参数和high参数是什么。 如果我假设它们是要排序的数组的最小和最大元素,那么if和else if语句没有任何意义,因为(data[i] < low)和(data[i] > high)总是返回零. 我哪里错了? 回答1 low和high是您为执行三向分区而定义的值,即要执行三向分区,您只需要两个值: [bottom] <= low < [middle] < high <= [top] 在 C++ 程序中,您移动的是分区发生的位置。 一个循序渐进的例子: data = [ 3, 1, 4, 9, 8, 2, 6, 9, 0 ] low = 4 high = 8 [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ] p^ i^ q^ [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ] p^ i^ q^ [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ] p^ i^ q^ [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ] p^ i^ q^ [ 3 , 1 , 4 , 0 , 8 , 2 , 6 , 9 , 9 ] p^ i^ q^ [ 3 , 1 , 0 , 4 , 8 , 2 , 6
  • 转载:《算法刷题LeetCode(中文版)》LeetCode题解,151道题完整版
    原始链接:https://blog.csdn.net/haimianjie2012/article/details/93344894?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.pc_relevant_is_cache&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.pc_relevant_is_cache LeetCode题解,151道题完整版 《算法刷题LeetCode(中文版)》 haimianjie2012 2019-06-22 18:16:25 6108 收藏 分类专栏: leetcode 文章标签: leetcode 数据结构 算法 数据库 版权 写在前面的话 该书包含了LeetCode Online Judge(http://leetcode.com/onlinejudge)所有题目的答案。 该书假定读者已经学过《数据结构》《算法》这两门课,熟练掌握C++或Java. 《数据结构》严蔚敏等著,清华大学出版社 《Algorithms》,Robert Sedgewick,Addison-Weslev
  • 荷兰国旗问题在 O(n) 中运行(Dutch National Flag Problem Running in O(n))
    问题