面试题3：数组中重复的数字

题目一：找出数组中重复的数字。

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

示例1：
输入长度为7的数组
[2, 3, 1, 0, 2, 5, 3]
那么对应的输出是重复的数字2或者3，数组内的数字大小都在0~6之间（包含）。

示例2：
输入长度为6的数组
[1, 2, 1, 4, 3, 5]
那么对应的输出是重复的数字1或者3

思路：

1、排序数组，然后对比前后数据是否一致。时间复杂度O(nlogn)，空间复杂度最好的情况O(1)；
2、遍历数组，将出现的数字保存到一个字典中，如果遍历到的数字存在于字典内，说明出现了重复的数字。时间复杂度O(n)，空间复杂度最差O(n)；
3、书中的解法：对数组进行排序，因为数据大小是0~n-1的，那么数组内的数字就可以和数组的下标对应起来，先将数组内数据进行交换排序，将数据放到对应的下标位置：

[2, 3, 1, 0, 2, 5, 3]
[1, 3, 2, 0, 2, 5, 3]
[3, 1, 2, 0, 2, 5, 3]
[0, 1, 2, 3, 2, 5, 3]

当遍历到第4个数2时，会跟2的下标进行交换，然后发现下标为2的位置已经有相同的数据，说明有重复。
代码如下：

func duplicate(_ nums: inout [Int]) -> (Bool, Int) { 
    if nums.isEmpty { 
        return (false, -1)
    }
    if nums.count == 1 {
        return (false, -1)
    }
    
    var index = 0
    var cur = 0
    var temp = 0
    while index < nums.count {
        cur = nums[index]
        if cur != index {
            temp = nums[cur]
            /* 
             如果交换的数所在的下标在排序好的下标之前，说明有重复
             如果交换的数和需要交换的数相同，说明有重复
            */
            if temp < index || temp == nums[temp] {
                return (true, temp)
            } else {
                // 交换2个数据
                nums[index] = temp
                nums[cur] = cur
            }
        }else {
            index += 1
        }
    }
    
    return (false, -1)
}

该解法时间复杂度O(n)，空间复杂度O(1)。

题目二：不修改数组找出重复的数字

在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。

例如,如果输入长度为8的数组
[2,3,5,4,3,2,6,7]
输出是重复的数字2或者3。

思路：

解法利用了二分查找的思想，扫描区间内数字的数量进行对比得到的重复数字。原理就是，如果不存在重复的情况下，区间内的数字总是数量count是小于等于区间mid - l + 1大小的，比如1~4之间的数的数量不重复的情况下最大就是1-4这4个数，那么如果超过4个数，肯定存在重复：

    func getDuplication(_ nums: [Int]) -> Int {
        
        guard nums.count > 1 else {
            return -1
        }
        
        var l = 1, r = nums.count - 1, mid = 0
        
        while l <= r {
            mid = l + (r - l) >> 1
            // 计算l~mid中间的数有多少个
            var count = 0
            for i in 0..<nums.count {
                if nums[i] >= l && nums[i] <= mid {
                    count += 1
                }
            }
            // 搜索完所有区间
            if l == r {
                if count > 1 { // 定位到重复的数字
                    return l
                } else {
                    break
                }
            }
            // 如果中间数字的数量大于正常数量，说明有重复，r左移，从左边继续搜索
            if count > (mid - l + 1) {
                r = mid
            }else { // 从右边搜索，l右移
                l = mid + 1
            }
        }
        
        return -1
    }

时间复杂度O(nlogn)，空间复杂度O(1)。

另外附上二分查找代码：


     /*
     标准二分查找：输入有序数组和查找的数，返回所在的index，如果不存在返回-1
     */
    func binarySearch(_ nums: [Int], target: Int) -> Int {
        if nums.count == 0 {
            return -1
        }
        if nums.count == 1 {
            if nums[1] == target { return 0 }
        }
        
        var l = 0
        var r = nums.count - 1
        var mid = 0
        
        while l <= r {
            mid = l + (r - l) / 2
            if nums[mid] == target {
                return mid
            } else if (nums[mid] > target) {
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        
        return -1
    }

PS：因为语言与官方不同，写法略有区别，单元测试量不够，如有错误，请留言指出。

最后编辑于：2019.06.27 16:03:12