[Swift]LeetCode961. 重复 N 次的元素 | N-Repeated Element in Size 2N Array

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10165080.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

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

Example 2:

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

Example 3:

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

Note:

4 <= A.length <= 10000
0 <= A[i] < 10000
A.length is even

在大小为 2N 的数组 A 中有 N+1 个不同的元素，其中有一个元素重复了 N 次。

返回重复了 N 次的那个元素。

示例 1：

输入：[1,2,3,3]
输出：3

示例 2：

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

示例 3：

输入：[5,1,5,2,5,3,5,4]
输出：5

提示：

4 <= A.length <= 10000
0 <= A[i] < 10000
A.length 为偶数

276ms

 1 class BitVector {
 2   private let wordSize: Int = 64
 3   var vector: [Int]
 4   
 5   init(size: Int) {
 6     let count = abs(size/wordSize)+1
 7     vector = Array(repeating: 0, count: count)
 8   }
 9   
10   func setBit(int: Int) -> Bool {
11     let wordIndex = abs(int/wordSize)
12     let word = vector[wordIndex]
13     let mask = 1 << (int%wordSize)
14       
15     if word & mask != 0 {
16       return false
17     } else {
18       vector[wordIndex] = word | mask
19     }
20     return true
21   }
22 }
23 
24 class Solution {
25     func repeatedNTimes(_ A: [Int]) -> Int {
26         let bitVector = BitVector(size: 10000)
27         for a in A {
28             if !bitVector.setBit(int: a) {
29                 return a
30             }
31         }
32         return -1
33     }
34 }

280ms

 1 class Solution {
 2     func repeatedNTimes(_ A: [Int]) -> Int {
 3         var dict : [Int: Int] = [:]
 4         for i in A {
 5             dict[i] = (dict[i] ?? 0) + 1
 6             if dict[i] == 2 {
 7                 return i
 8             }
 9         }
10         return -1
11     }
12 }

280ms

 1 class Solution {
 2     func repeatedNTimes(_ A: [Int]) -> Int {
 3         var set:Set<Int> = Set<Int>()
 4         for x in A
 5         {
 6             if set.contains(x)
 7             {
 8                 return x
 9             }
10             set.insert(x)
11         }
12         return -1
13     }
14 }

300ms

 1 class Solution {
 2     func repeatedNTimes(_ A: [Int]) -> Int {
 3         var n:Int = A.count
 4         var f:[Int] = [Int](repeating:0,count:100000)
 5         for v in A
 6         {
 7             f[v] += 1
 8         }
 9         
10         for i in 0..<100000
11         {
12             if f[i] > 1
13             {
14                 return i
15             }
16         }
17         return -1
18     }
19 }

316ms

 1 class Solution {
 2     func repeatedNTimes(_ A: [Int]) -> Int {
 3         let aDict = Dictionary( A.map{ ($0, 1) }, uniquingKeysWith: +)
 4         for (key, value) in aDict {
 5             if value >= 2 {
 6                 return key
 7             }
 8         }
 9         return -1
10     }
11 }

336ms

1 class Solution {
2     func repeatedNTimes(_ A: [Int]) -> Int {
3         var counts = [Int : Int]()
4         
5         A.forEach( { counts[$0, default: 0] += 1 })
6         
7         return counts.max(by: {a, b in a.value < b.value })!.key
8     }
9 }

396ms

 1 class Solution {
 2     func repeatedNTimes(_ A: [Int]) -> Int {
 3        
 4         var numSet : Set<Int> = []
 5         
 6         for num in A.sorted()[0...A.count/2+1]
 7         {
 8             if numSet.contains(num)
 9             {
10                 return num
11             }
12             numSet.insert(num)
13         }
14         return 0
15     }
16 }