【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——队列 以下代码大部分为本人所写,少部分为官方示例代码。 题目: 题解:前后指针。前指针指向最后一个个节点时,后指针指向了中间节点。 题目: 题解:双指针,分别指向奇数节点和偶数节点,然后再串起来

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

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

    2024年02月12日
    浏览(35)
  • 力扣75——图广度优先搜索

    总结leetcode75中的 图广度优先搜索 算法题解题思路。 上一篇:力扣75——图深度优先搜索 题目: 题解: 广度优先搜索 。 将与入口相邻的空格子压入队列。 然后用 while循环 遍历队列中的格子,每个访问过的格子都要做标记(记录它到入口的距离,并将状态设置为已访问)。

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

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

    2024年02月12日
    浏览(40)
  • 【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日
    浏览(32)
  • 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日
    浏览(30)
  • 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日
    浏览(36)
  • 力扣经典150题第三十题:长度最小的子数组

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

    2024年04月23日
    浏览(49)
  • LeetCode75——Day21

    1207. Unique Number of Occurrences Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise. Example 1: Input: arr = [1,2,2,1,1,3] Output: true Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences. Example 2: Input: arr = [1,2

    2024年02月07日
    浏览(75)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包