【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题)

这篇具有很好参考价值的文章主要介绍了【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题),LeetCode刷题,leetcode,算法,c语言,动态规划,数据结构

目录

1、题目介绍

2、解题思路

2.1、冒泡排序暴力破解

2.2、快速排序的子过程partition

2.2.1、详细过程描述

2.2.2、代码描述


【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题),LeetCode刷题,leetcode,算法,c语言,动态规划,数据结构

1、题目介绍

原题链接:75. 颜色分类 - 力扣(LeetCode)

【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题),LeetCode刷题,leetcode,算法,c语言,动态规划,数据结构

示例 1:

输入:nums = [2,0,2,1,1,0]

输出:[0,0,1,1,2,2]

示例 2:

输入:nums = [2,0,1]

输出:[0,1,2]

 提示:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

2、解题思路

根据题目的意思,简单来说就是将数组里的数据按照0、1、2的顺序排列。

如果只是要求排序,其实投机取巧的方式很多,比如直接使用冒泡排序也能完成此题。

2.1、冒泡排序暴力破解

void sortColors(int* nums, int sz) {
	int i = 0;
	int j = 0;
	for (i = 0; i < sz - 1; i++)
	{
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (nums[j] > nums[j + 1])
			{
				int tmp = nums[j];
				nums[j] = nums[j + 1];
				nums[j + 1] = tmp;
			}
		}
	}
}

冒泡排序:时间复杂度为O(n^2),空间复杂度为O(1)

2.2、快速排序的子过程partition

但是根据题目的难度标识为中等,很明显这道题不是在考察冒泡排序的。 

该题的难点在于如何原地遍历的情况下使得:时间复杂度为O(n),空间复杂度为O(1)。即仅使用常数空间的一趟扫描算法。

而这里就用到了快速排序的子过程partition,partition能够通过一次遍历将所有元素按照标志数进行划分,小于放标志数左边,大于放标志数右边。

首先这里有个数组,规定小num的值放在左侧,大于num的值放在右侧,而等于num的值放在中间,下面进行partition过程讲解。

【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题),LeetCode刷题,leetcode,算法,c语言,动态规划,数据结构

首先蓝色方框是小于num的区域,橙色方框是大于num的区域,i从0开始循环遍历。

规则:

  1. 当arr[ i ]小于num时,arr[ i ]与小于区域的下一个元素交换位置,然后小于区域向右移动一位,i++。
  2. 当arr[ i ]等于num时,i++。
  3. 当arr[ i ]大于num时,arr[ i ]与大于区域的上一个元素交换位置,然后大于区域向左移动一位,此时i不自增
2.2.1、详细过程描述

首先arr[ i ] 等于3,小于5

【执行规则1】3与小于区域的下一位元素交换位置,而此时小于区域的下一个元素就是3,因此交换其实已经完成了。然后小于区域向右移动一位,i++。

【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题),LeetCode刷题,leetcode,算法,c语言,动态规划,数据结构

 此时arr[ i ] 等于5

【执行规则2】直接 i++。

【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题),LeetCode刷题,leetcode,算法,c语言,动态规划,数据结构

此时arr[ i ] 等于6,大于5

【执行规则3】3与大于区域的上一位元素交换位置,于是6和8交换位置。然后大于区域向左移动一位。

【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题),LeetCode刷题,leetcode,算法,c语言,动态规划,数据结构

 此时arr[ i ] 等于8,大于5

【执行规则3】8与大于区域的上一位元素交换位置,于是8和第二个5交换位置。然后大于区域向左移动一位。

【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题),LeetCode刷题,leetcode,算法,c语言,动态规划,数据结构

 此时arr[ i ] 等于5

【执行规则2】直接 i++。

【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题),LeetCode刷题,leetcode,算法,c语言,动态规划,数据结构

 此时arr[ i ] 等于7,大于5

【执行规则3】7与大于区域的上一位元素交换位置,于是7和第二个3交换位置。然后大于区域向左移动一位。

【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题),LeetCode刷题,leetcode,算法,c语言,动态规划,数据结构

此时arr[ i ] 等于3,小于5

【执行规则1】3与小于区域的下一位元素交换位置,于是第一个5和第二个3交换位置。然后小于区域向右移动一位,i++。

【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题),LeetCode刷题,leetcode,算法,c语言,动态规划,数据结构

 此时arr[ i ] 等于4,小于5

【执行规则1】4与小于区域的下一位元素交换位置,于是第一个5和4交换位置。然后小于区域向右移动一位,i++。

【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题),LeetCode刷题,leetcode,算法,c语言,动态规划,数据结构

此时i遇到了大于区域了,就停止执行,此时数组中的值就变成了左边小右边大中间等于。

2.2.2、代码描述

按照快速排序的子过程partition的方法,改造代码 ,使标志数为1,然后将小于1的放左边,大于1的放右边,既完成排序。

void sortColors(int* nums, int numsSize){
    int signal  =  1;  //标志数
    int i = 0;
    int left = -1; //left为下标,是小于区域的右边界,刚开始还未进入数组,因此为-1
    int right = numsSize; //right为下标,是大于区域的左边界,刚开始还未进入数组,因此为numsSize
    while(i<right)   //当i遇上大于区域时停止循环,此时就完成了排序
    {
        if(nums[i] < signal)  //当nums[i]小于标志数
        {
            int tmp = nums[left+1];   //交换小于区域的下一个元素
            nums[left+1] = nums[i];
            nums[i] =  tmp;
            left++;
            i++;
        }
        else if(nums[i] > signal)  //当nums[i]大于标志数
        {
            int tmp = nums[right-1];  //交换大于区域的上一个元素
            nums[right-1] = nums[i];
            nums[i] = tmp;
            right--;
            
        }
        else
        {
            i++;   //等于时直接i++
        }
    }
}

快速排序的子过程partition:时间复杂度为O(n),空间复杂度为O(1) 

【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题),LeetCode刷题,leetcode,算法,c语言,动态规划,数据结构

【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题),LeetCode刷题,leetcode,算法,c语言,动态规划,数据结构

如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!文章来源地址https://www.toymoban.com/news/detail-714536.html

如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!

如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!

到了这里,关于【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣75——哈希表/哈希集合

    总结leetcode75中 哈希表/哈希集合 的算法题解题思路。 上一篇:力扣75——滑动窗口 以下代码大部分为本人所写,少部分为官方示例代码。 题目: 题解:先用哈希表分别记录各自的元素,然后各自检测是否有不存在于对方的元素。 题目: 题解:先用unordered_map记录每个字母出

    2024年02月16日
    浏览(32)
  • 力扣75——堆/优先队列

    总结leetcode75中的 堆/优先队列 算法题解题思路。 上一篇:力扣75——图广度优先搜索 题目: 题解: 最大堆 。 建立最大堆。然后依次取出k-1个,每取一个就重新修复最大堆。最后堆顶元素即为所求值。 题目: 题解: 用set类型的s记录被删除的变量。用minV记录最小值。 如果

    2024年02月12日
    浏览(33)
  • 力扣75——前缀树

    总结leetcode75中的 前缀树 算法题解题思路。 上一篇:力扣75——位运算 题目: 题解: 前缀树。对于每个类对象trie,它有一个长度为26的vectorTrie*,记录着当前节点之后是否还存在哪些字母,如果不存在则是空指针。此外还有一个bool类型的isEnd,它记录当前节点是否为某个字符

    2024年02月12日
    浏览(34)
  • 力扣75——二分查找

    总结leetcode75中的 二分查找 算法题解题思路。 上一篇:力扣75——堆/优先队列 题目: 题解: 二分查找。用 left 、 right 分别记录左端点和右端点。然后计算出它们的平均值 mid ,接着用 guess(mid) 判断是大了还是小了。 题目: 题解: 先 快速排序 ,然后用 upper_bound() 找到第一

    2024年02月12日
    浏览(37)
  • 【leetcode 力扣刷题】数学题之除法:哈希表解决商的循环节➕快速乘求解商

    题目链接:166. 分数到小数 题目内容: 题目是要我们把一个分数变成一个小数,并以字符串的形式返回。按道理,直接将分子numerator除以分母denominator就得到了小数,转换成string返回就好。题目要求里指出了特殊情况—— 小数部分如果有循环,就把循环节括在括号里 。 那么

    2024年02月10日
    浏览(39)
  • 78-快速排序练习-LeetCode面试题17.14.最小k个数

    题目 设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。 示例: 输入: arr = [1,3,5,7,2,4,6,8], k = 4 输出: [1,2,3,4] 提示:     0 = len(arr) = 100000     0 = k = min(100000, len(arr)) 思路 注意到题目要求「任意顺序返回这 k 个数即可」,因此我们只需要确保前 k 小的

    2023年04月12日
    浏览(31)
  • leetcode - 86. Partition List

    Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. Example 1: Example 2: Constraints: Use two list node and two tail node for smaller nodes and bigger nodes. Every time add the node

    2024年02月12日
    浏览(28)
  • LeetCode //C - 86. Partition List

    Given the head of a linked list and a value x , partition it such that all nodes less than x come before nodes greater than or equal to x . You should preserve the original relative order of the nodes in each of the two partitions.   Example 1: Input: head = [1,4,3,2,5,2], x = 3 Output: [1,2,2,4,3,5] Example 2: Input: head = [2,1], x = 2 Output: [1,2] Const

    2024年02月10日
    浏览(34)
  • 力扣经典150题第三十题:长度最小的子数组

    1. 介绍 在本篇文章中,我们将解析力扣经典150题中的第三十题:长度最小的子数组。题目要求找出数组中满足其总和大于等于目标值 target 的长度最小的连续子数组,并返回其长度。 2. 问题描述 给定一个含有 n 个正整数的数组 nums 和一个正整数 target ,找出该数组中满足其总

    2024年04月23日
    浏览(48)
  • LeetCode75——Day27

    933. Number of Recent Calls You have a RecentCounter class which counts the number of recent requests within a certain time frame. Implement the RecentCounter class: RecentCounter() Initializes the counter with zero recent requests. int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests

    2024年02月05日
    浏览(27)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包