【python-时空最优两种实现】不修改数组找出重复的数字
时间复杂度最优的算法:time O(n), space O(n)
见下文中注释部分
空间复杂度最优的算法:time O(nlogn), space O(1)
class Solution(object):
# # time O(n), space O(n)
# def duplicateInArray(self, nums):
# """
# :type nums: List[int]
# :rtype int
# """
# n = len(nums)
# res = -1
# copy_nums = [_ for _ in nums]
# for i, v in enumerate(copy_nums):
# while v != i:
# if v >= n:
# return -1
# if copy_nums[v] == v:
# res = v
# break
# else:
# copy_nums[v], copy_nums[i] = copy_nums[i], copy_nums[v]
# v = copy_nums[i]
# return res
# time O(nlogn), space O(1)
def duplicateInArray(self, nums):
"""
:type nums: List[int]
:rtype int
"""
n = len(nums)
l, r = 1, n-1
while l<r:
count = 0
mid = l+r >> 1
for v in nums:
if l<=v<=mid:
count += 1
if count > mid-l+1:
r = mid
else:
l = mid + 1
return l
"""
if __name__ == '__main__':
sol = Solution()
# data = [2, 3, 5, 4, 3, 2, 6, 7]
# data = [2, 3, 2, 1]
data = [2, 3, 3, 1]
print(sol.duplicateInArray(data))
"""