• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode961.重复N次的元素|N-RepeatedElementinSize2NArray

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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:

  1. 4 <= A.length <= 10000
  2. 0 <= A[i] < 10000
  3. 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

提示:

  1. 4 <= A.length <= 10000
  2. 0 <= A[i] < 10000
  3. 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap