Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >常见编程模式之循环排序

常见编程模式之循环排序

作者头像
口仆
发布于 2020-09-14 07:32:20
发布于 2020-09-14 07:32:20
1.9K01
代码可运行
举报
运行总次数:1
代码可运行

5. 循环排序(Cyclic Sort)

基本原理及应用场景

循环排序模式描述了一种解决包含给定范围数字的数组问题的有趣方法。具体来说,我们遍历数组的每一位数字,如果当前数字不在正确的索引上,则将其与正确的索引交换,如下图所示。如果直接把每个数字放到正确的索引上,会产生平方级的时间复杂度,而循环排序模式则可以提供线性的时间复杂度。

在以下场景中,我们可能会用到循环排序模式:

  • 问题涉及给定范围的排序数组
  • 问题需要找出排序数组中的缺失/重复/最小值

经典例题

268. 缺失数字(Easy)

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

「示例」

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: [3,0,1]
输出: 2

本题可以采用循环排序模式求解。我们遍历数组的每一位数字,判断其是否位于正确的索引上。遍历完成后再一次遍历数组,找出索引与值不相等的数字即为缺失数字。具体的代码实现如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        start = 0
        while start < len(nums):
            num = nums[start]
            if num < len(nums) and num != start: # 可以换成 nums[num] != num
                # 可能执行多次交换,否则存在不完全排序
                nums[start], nums[num] = nums[num], nums[start]
            else:
                start += 1
        for i in range(len(nums)): # 遍历数组找出缺失数字
            if nums[i] != i:
                return i
        return len(nums) # 可能缺失的为最后一位

这道题还有一些其他的解法,比较巧妙的是位运算和数学解法。位运算的思路为对一个数进行两次完全相同的异或运算会得到原来的数,因此将

[0, \ldots,n]

与输入数组进行异或,最终的结果即为异或的数字。实际操作时可以通过一次循环完成所有的异或运算(将每一个数与其下标进行异或,初始值为

n

):

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def missingNumber(self, nums):
        missing = len(nums)
        for i, num in enumerate(nums):
            missing ^= i ^ num
        return missing

数学解法则是直接基于高斯求和公式求出

[0,\ldots,n]

的和,减去数组中所有数的和,即为缺失数字:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def missingNumber(self, nums):
        expected_sum = len(nums)*(len(nums)+1)//2
        actual_sum = sum(nums)
        return expected_sum - actual_sum
442. 数组中重复的数据(Medium)

给定一个整数数组 a,其中 1 ≤ a[i] ≤ n(n 为数组长度), 其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。 你可以不用到任何额外空间并在 O(n) 时间复杂度内解决这个问题吗?

「示例」

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:
[4,3,2,7,8,2,3,1]

输出:
[2,3]

本题可以使用循环排序求解。利用数组的下标(注意要减 1)对其进行遍历排序,交换索引与值不相等的元素,最后遍历数组输出即可。具体代码实现如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        start = 0
        res = []
        while start < len(nums): # 用for循环也可
            num = nums[start]
            # 注意判断条件的设置,当前位的数字对应的索引指向的数字不符合要求时交换
            if nums[num - 1] != num: # 用start比可能陷入死循环,因为存在重复数字
                nums[start], nums[num - 1] = nums[num - 1], nums[start]
            else:
                start += 1
        for i in range(len(nums)):
            if nums[i] != i + 1:
                res.append(nums[i])
        return res

还有一种比较巧妙的解法是考虑到元素最多出现两次,因此可以通过遍历数组对当前值对应的索引进行符号翻转,只有出现两次的元素会查询到负值。具体代码实现如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        for i in range(len(nums)):
            index = abs(nums[i]) -1 # 可能已经为负了
            if nums[index] > 0: # 大于0说明当前值还未被翻转(即第一次查询)
                nums[index] *= -1
            else: # 否则是第二次查询,该元素必重复出现
                res.append(index + 1)
        return res
41. 缺失的第一个正数(Hard)

给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。

「示例」

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: [1,2,0]
输出: 3

这道题也可以使用循环排序求解,思路与上一题基本一致:假定数组包含

x \in [1, N]

,将数组中的数移到其对应的索引的位置,恢复后再遍历数组即可找到第一个缺失的正数。代码实现如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

这道题也可以利用索引对数组进行标记,具体思路如下图所示:

代码实现如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            if nums[i] <= 0:
                nums[i] = n + 1  
        for i in range(n):
            num = abs(nums[i])
            if num <= n:
                nums[num - 1] = -abs(nums[num - 1]) # 防止重复元素,保证为负
        for i in range(n):
            if nums[i] > 0:
                return i + 1   
        return n + 1

其他类似的题目列表:

  • LeetCode 448-「找到所有数组中消失的数字」(Easy)
  • LeetCode 645-「错误的集合」(Easy)
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-09-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 口仆 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
这道算法题太太太太太简单啦
题目来源于 LeetCode 上第 268 号问题:缺失数字。题目难度为 Easy,目前通过率为 50.2% 。
五分钟学算法
2019/05/21
4140
这道算法题太太太太太简单啦
【优选算法篇】探索位运算的宇宙:简单规则背后的复杂逻辑(中篇)
接上篇:【优选算法篇】位运算小课堂:从入门到精通的奇妙之旅(上篇)-CSDN博客
熬夜学编程的小王
2024/12/24
1120
【优选算法篇】探索位运算的宇宙:简单规则背后的复杂逻辑(中篇)
初识算法 · 位运算(2)
​本文的主题是位运算,通过四道题目讲解,一道是判断字符是否唯一,一道是只出现一次的数字III,一道是比特位计数,一道是丢失的数字。 链接分别为:
_lazy
2024/11/19
810
初识算法 · 位运算(2)
LeetCode-面试题53-2-0到n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
benym
2022/07/14
5510
LeetCode 热题 100 - 只出现一次的数字
 ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
陈明勇
2025/01/31
15412
leetcode刷题:消失的数字
数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?
see.
2024/06/04
910
剑指 Offer 53 - II. 0~n-1中缺失的数字
【1】最简单的直接遍历的方式:这个思路是基于,首先一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内,这就说明了这是一串连续的数字,且会与下标有一定联系,当不缺失的时候,下标与数值一 一对应,故直接遍历且比对下标即可。
忧愁的chafry
2023/03/08
2260
剑指 Offer 53 - II. 0~n-1中缺失的数字
LeetCode数组高频题目整理
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
嵌入式与Linux那些事
2021/05/20
1.6K0
LeetCode数组高频题目整理
常见编程模式之双指针
双指针模式指使用两个一前一后的指针遍历数据结构,直到某个指针触发停止条件。该模式常用于在有序数组或链表中搜索元素对。使用双指针的好处在于和单指针相比,不用去连续遍历整个数组来找出答案,可以带来更好的时间或空间复杂度。
口仆
2020/08/14
2K0
深度解析算法之位运算
<< 左移操作符 > >右移操作符号 ~取反 &按位与:有0就是0 |按位或:有1就是1 ^按位异或:相同为0,不用的话就是1 /无进位相加
Undoom
2025/04/22
1430
深度解析算法之位运算
【优选算法篇】揭秘快速排序:分治算法如何突破性能瓶颈(上篇)
分治法是一种非常高效的算法设计策略,广泛应用于计算机科学的多个领域,尤其是在解决复杂问题时,它通过将大问题拆解成更小的子问题来降低问题的复杂度。快速排序(QuickSort)是分治法中的经典例子,能够在许多实际场景中提升性能。它的重要性体现在以下几个方面:
熬夜学编程的小王
2024/12/24
980
【优选算法篇】揭秘快速排序:分治算法如何突破性能瓶颈(上篇)
【算法一周目】位间流转,数字律动——洞察 C++ 位运算中的精妙与哲思
次,逐位进行比较;也可以使用上面提到的消除一个数二进制最低位1的操作,统计多少次操作后
HZzzzzLu
2025/01/08
510
【优选算法篇】位运算小课堂:从入门到精通的奇妙之旅(上篇)
位运算(Bitwise Operation)是计算机底层操作的核心。它的重要性体现在以下几个方面:
熬夜学编程的小王
2024/12/24
1110
【优选算法篇】位运算小课堂:从入门到精通的奇妙之旅(上篇)
一文带你AC四道题【位运算】
我这里总结了几道位运算的题目分享给大家,分别是 136和137, 260 和 645, 总共加起来四道题。 四道题全部都是位运算的套路,如果你想练习位运算的话,不要错过哦~~
lucifer210
2020/03/26
4150
【优选算法篇】计算机背后的秘密武器:位运算的超能力(下篇)
接上篇:【优选算法篇】探索位运算的宇宙:简单规则背后的复杂逻辑(中篇)-CSDN博客
熬夜学编程的小王
2024/12/24
1160
【优选算法篇】计算机背后的秘密武器:位运算的超能力(下篇)
Leetcode【26、80、962】
这道题是给一个排序好的数组,通过修改原数组,使得前 K 个元素都不同,返回 K,要求使用 O(1) 的空间。
echobingo
2019/07/15
6280
LeetCode-136. 只出现一次的数字(java)
       这题相对其他简答题还要简答,所以题目难度我给了一星,分析题意可得要求找出只出现一次的那个数字,那么通常能想到的实现方式有哪些呢?(除了双层循环嵌套暴力法啊)
bug菌
2023/05/27
2620
LeetCode-136. 只出现一次的数字(java)
【优选算法篇】剥洋葱式探索:用二分查找精准定位答案(下篇)
接上篇:【优选算法篇】寻找隐藏的宝藏:用二分查找打开算法世界的大门(上篇)-CSDN博客
熬夜学编程的小王
2024/12/24
630
【优选算法篇】剥洋葱式探索:用二分查找精准定位答案(下篇)
【优选算法篇】微位至简,数之恢宏——解构 C++ 位运算中的理与美
利用「位图」的思想,每一个「比特位」代表一个「字符」,一个 int 类型的变量的 32 位足够表示所有的小写字母。在位图中,如果一个比特位是 0,表示这个字符没有出现过;如果一个比特位是 1,表示该字符出现过。
半截诗
2024/11/21
1250
LeetCode通关:数组十七连,真是不简单
数组基本上是我们最熟悉的数据结构了,刚会写“Hello World”不久,接着就是“杨辉三角”之类的练习。
三分恶
2021/08/10
3960
推荐阅读
相关推荐
这道算法题太太太太太简单啦
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验