[swift] 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2] Output: 2

1	Input: [1,3,4,2,2] Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

1 2	Input: [3,1,3,4,2] Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n²).
There is only one duplicate number in the array, but it could be repeated more than once.

func findDuplicate(_ nums: [Int]) -> Int {
    let sn = nums.sorted()
    var i = 1
    while i < nums.count {
        if sn[i-1] == sn[i] { return sn[i] }
        i += 1
    }

    return -1
}

func findDuplicate(_ nums: [Int]) -> Int {

let sn = nums.sorted()

var i = 1

while i < nums.count {

if sn[i-1] == sn[i] { return sn[i] }

i += 1

}

return -1

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版