数组中重复的数字

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

在一个长度为 n 的数组里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组 {2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或3。

从头到尾依次扫描这个数组中的每个数字。当扫描到下标为i的数字时，首先比较这个数字（用m表示）是不是等于i。如果是，则接着扫描下一个数字；如果不是，则再拿它和第m个数字进行 化较。如果它和第m个数字相等，就找到了一个重复的数字（该数字在下标为i和m的位置都出现了）；如果它和第m个数字不相等，就把第i个数字和第m个数字交换，把m放到属于它的位置。接下来再重复这个比较、交换的过程，直到我们发现一个重复的数字。

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

func duplicate(numbers: inout [Int]) -> (Bool, Int?) {
    // 所有数字都在 0~n-1 的范围内
    guard numbers.allSatisfy({ $0 >= 0 }),
          numbers.allSatisfy({ $0 <= numbers.count - 1 })
    else { return (false, nil) }
    
    for i in 0..<numbers.count {
        while numbers[i] != i {
            if numbers[i] == numbers[numbers[i]] {
                return (true, numbers[i])
            }
            
            let temp = numbers[i]
            numbers[i] = numbers[temp]
            numbers[temp] = temp
        }
    }
    
    return (false, nil)
}

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

在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组 {2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3。

我们把从1~n的数字从中间的数字m分为两部分，前面一半为1~m，后面一半为m+1~n。如果1到m的数字的数目超过m，那么这一半的区间里一定包含重复的数字；否则，另一半m+1~n的区间里一定包含重复的数字。我们可以继续把包含重复数字的区间一分为二，直到找到一个重复的数字。

时间复杂度O(nlogn)，空间复杂度O(1)。不能保证找出所有重复的数字。

func getDuplication(numbers: [Int]) -> Int {
    // 所有数字都在1~n的范围内
    guard numbers.allSatisfy({ $0 >= 1 }),
          numbers.allSatisfy({ $0 <= numbers.count })
    else { return -1 }
    
    var start = 1
    var end = numbers.count - 1
    
    while end >= start {
        
        let middle = ((end - start) >> 1) + start
        let count = countRange(numbers: numbers, start: start, end: middle)
        
        if end == start {
            if count > 1 {
                return start
            } else {
                break
            }
        }
        
        if count > (middle - start + 1) {
            end = middle
        } else {
            start = middle + 1
        }
    }
    
    return -1
}

func countRange(numbers: [Int], start: Int, end: Int) -> Int {
    guard !numbers.isEmpty else { return 0 }
    
    var count: Int = 0
    for i in 0..<numbers.count {
        if numbers[i] >= start, numbers[i] <= end {
            count += 1
        }
    }
    
    return count
}

摘抄资料：《剑指offer》