每日一道算法之--数组中的重复数字

数组

Word count: 714Reading time: 2 min

 2020/03/09   Share

数组中重复的数字

力扣面试题03 : https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：

2 <= n <= 100000

这是剑指offer里面的原题,也是比较简单的一道题,但是,一开始我能想到的就是通过排序然后遍历就能够找到重复的数字,时间复杂度为O(logn),或者通过哈希表建立索引,从而使时间复杂度变为O(n),但是要牺牲额外的空间.然后作者给我们提供了一种很好的方法,我暂且叫做下标定位法.看看是怎么实现的吧

1. 排序实现

直接看代码:

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        if not nums: return -1
        if len(nums) == 1: return 
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return nums[i]
        return -1

2. 利用哈希表实现

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        if not nums: return -1
        if len(nums) == 1: return -1
        has_map = {}
        for num in nums:
            if num in has_map:
                return num
            has_map[num] = 1
        return -1

3. 下标定位实现

阅读题目可以发现,所有数字都在 0～n-1 的范围内(哈哈我感觉其实救赎出题人有意而为), 这就可以假设如果数组中没有重复的数字, 那么排好序之后,数组每一个下标对应的数,其实就是刚好等于下标的,看到这句话,卧槽,牛逼牛逼!!如果有重复的数,则有些下标可能存在多个数,有的下标可能没有数。
现在可以重新对这个数组排序,从下标为i开始,这个数字为m,如果m不为i,则将a[i]与a[m]比较,如果不相等,则交换;如果相等,则证明找到了重复的数字。这样,下标为m的数它的值也为m了,相当于每个数最多两次交换就能找到它对应的下标.

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            while nums[i] != i:
                if nums[i] == nums[nums[i]]:
                    return nums[i]
                nums[nums[i]], nums[i] = nums[i], nums[nums[i]] 
        return -1

3.1 复杂度分析

时间复杂度:虽然代码中有两层循环,但是每个数最多两次交换就能找到它对应的下标,所以时间复杂度还是为O(n)

空间复杂度:没有用到额外的数据结构,所以空间复杂度为O(1)

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/03/09/algorithm-Interview-03/

发表日期：March 9th 2020, 10:39:07 pm

更新日期：March 9th 2020, 10:40:55 pm

Next Post

《趣谈网络协议》学习笔记之--通信协议综述
Previous Post

学习笔记之---负载均衡

CATALOG

1. 数组中重复的数字

