2

循环排序的时间复杂度是 O(n^2)参考

但是，该解决方案声称以下涉及循环排序的算法仅使用 O(n)。时间复杂度不应该是 O(n^2) 吗？

    def find_all_missing_numbers(nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        i = 0

        # This is cycle sort and should use O(n^2)?!
        while i < len(nums):
            j = nums[i] - 1
            if nums[i] != nums[j]:
                nums[i], nums[j] = nums[j], nums[i]  # swap
            else:
                i += 1

        missingNumbers = []

        # O(n)
        for i in range(len(nums)):
            if nums[i] != i + 1:
                missingNumbers.append(i + 1)

        return missingNumbers
#

时间复杂度 = O(n^2 + n) = O(n^2)。解决方法错了吗？

4

2 回答 2

2

这不是循环排序，如果数组由 range 中的数字组成，则该算法旨在查找缺失的数字[1, len(array)]。

print(find_all_missing_numbers([5,4,3,2,1]))
print(find_all_missing_numbers([1,2,3,5,5]))
print(find_all_missing_numbers([2]))

[]
[4]
错误

这一行假设正确的位置是由一个存储的数字给出的，只有当数字在上面显示的范围内时，它才可能有效。

j = nums[i] - 1

而循环排序花费线性时间为每个数字寻找合适的位置。

于 2019-09-03T04:36:22.447 回答
1 
def find_all_missing_numbers(nums):

        i = 0 # Will happen only once so O(1)

        # no linear search for true position
        while i < len(nums):
            j = nums[i] - 1 # Will happen once per each iteration
            if nums[i] != nums[j]: # Condition Check Will happen once per iteration
                nums[i], nums[j] = nums[j], nums[i] # Will happen if if Condition is true so "c" times
            else: 
                i += 1 # Will happen if if Condition is not true so "c'" times

        missingNumbers = []

        # O(n)
        for i in range(len(nums)):
            if nums[i] != i + 1:
                missingNumbers.append(i + 1)

        return missingNumbers

所以 ：

1 + Len(nums)*(1 + 1 + c + c' + 1) + n

如果 Len(nums) = n 那么

1 + 3n + (c + c')n + n = 1 + (3+C)n + n ~ O(n)
于 2019-09-03T12:46:08.387 回答