专栏首页用户2133719的专栏常见编程模式之循环排序

常见编程模式之循环排序

5. 循环排序(Cyclic Sort)

基本原理及应用场景

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

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

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

经典例题

268. 缺失数字(Easy)

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

「示例」

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

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

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

):

class Solution:
    def missingNumber(self, nums):
        missing = len(nums)
        for i, num in enumerate(nums):
            missing ^= i ^ num
        return missing

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

[0,\ldots,n]

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

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) 时间复杂度内解决这个问题吗?

「示例」

输入:
[4,3,2,7,8,2,3,1]

输出:
[2,3]

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

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

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

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)

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

「示例」

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

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

x \in [1, N]

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

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

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

代码实现如下:

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)

本文分享自微信公众号 - 口仆(roito33),作者:口仆

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 常见编程模式之动态规划:0-1背包问题

    动态规划是编程问题中最常见的一种模式。本质上来说,动态规划是一种对递归的优化,通过记忆化存储的方式减少重复计算的次数。在尝试用动态规划解决问题时,我们可以遵循如...

    口仆
  • CS229 课程笔记之九:EM 算法与聚类

    为了证明 k-means 算法能否保证收敛,我们定义「失真函数」(distortion function)为:

    口仆
  • CS224N 课程笔记之二:词向量(下)

    之前我们介绍了两种表示词向量的方法:「基于数量」的矩阵分解方法(HAL & LSA)和「基于窗口」的概率方法(word2vec)。第二种方法明显优于第一种,但其...

    口仆
  • LeetCode---两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    TrueDei
  • 一天一大 leet(计算右侧小于当前元素的个数)难度:困难-Day20200711

    给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质:counts[i] 的值是 nums[i] 右侧小于 nu...

    前端小书童
  • 【leetcode刷题】T9-寻找旋转排序数组中的最小值

    今天分享leetcode第9篇文章,也是leetcode第153题—寻找旋转排序数组中的最小值,地址是:https://leetcode.com/problem...

    木又AI帮
  • LeetCode 457. 环形数组循环(暴力+快慢指针)

    给定一个含有正整数和负整数的环形数组 nums。 如果某个索引中的数 k 为正数,则向前移动 k 个索引。相反,如果是负数 (-k),则向后移动 k 个索引。...

    Michael阿明
  • LeetCode 154. 寻找旋转排序数组中的最小值 II(二分查找)

    ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

    Michael阿明
  • LeetCode 两数之和 Python

  • LintCode-5.第k大元素

    给出数组 [1,2,3,4,5],第一大的元素是 5,第二大的元素是 4,第三大的元素是 3,以此类推

    悠扬前奏

扫码关注云+社区

领取腾讯云代金券