[Swift]LeetCode697.数组的度|DegreeofanArray

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a non-empty array of non-negative integers nums, the degreeof this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

Input: [1, 2, 2, 3, 1]
Output: 2
Explanation: 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.

Example 2:

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

Note:

nums.length will be between 1 and 50,000.
nums[i] will be an integer between 0 and 49,999.

给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1:

输入: [1, 2, 2, 3, 1]
输出: 2
解释: 
输入数组的度是2，因为元素1和2的出现频数最大，均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2，所以返回2.

示例 2:

输入: [1,2,2,3,1,4,2]
输出: 6

注意:

nums.length 在1到50,000区间范围内。
nums[i] 是一个在0到49,999范围内的整数。

Runtime: 220 ms

Memory Usage: 20.5 MB

 1 class Solution {
 2     func findShortestSubArray(_ nums: [Int]) -> Int {
 3         guard nums.count > 1 else {
 4             return nums.count
 5         }
 6         var dic: [Int:Int] = [:]
 7         for i in 0..<nums.count {
 8             let num: Int = nums[i]
 9             if dic.keys.contains(num) {
10                 dic[num] = dic[num]! + 1
11             } else {
12                 dic[num] = 1
13             }
14         }
15         var max = 0//出现最大次数
16         var maxNums: [Int] = []//出现最大次数元素数组
17         for j in dic.keys {
18             let v = dic[j]!
19             if v > max {
20                 maxNums.removeAll()
21                 maxNums.append(j)
22                 max = v
23             } else if v == max {
24                 maxNums.append(j)
25             }
26         }
27         if max < 2 {
28             return 1
29         }
30         var minChildArrayCount = nums.count//最短连续子数组长度
31         for a in maxNums {
32             var start: Int = 0,end: Int = nums.count-1//开始位置，结束位置
33             for s in nums {
34                 if s != a {
35                     start += 1
36                 } else {
37                     break
38                 }
39             }
40             for e in nums.reversed() {
41                 if e != a {
42                     end -= 1
43                 } else {
44                     break
45                 }
46             }
47             minChildArrayCount = min(minChildArrayCount, end-start+1)
48         }
49         return minChildArrayCount
50     }
51 }

228ms

 1 class Solution {
 2     func findShortestSubArray(_ nums: [Int]) -> Int {        
 3         var starts = [Int: Int]()
 4         var ends = [Int: Int]()
 5         var counts = [Int: Int]()
 6         var maxCount = Int.min
 7         
 8         for i in 0..<nums.count {            
 9             let num = nums[i]
10             if starts[num] == nil {
11                 starts[num] = i
12             }
13             ends[num] = i
14             counts[num] = ( counts[num] ?? 0 ) + 1            
15             maxCount = max(counts[num]!, maxCount)
16         }        
17 
18         var result = Int.max
19         for key in counts.keys {            
20             if counts[key]! < maxCount {
21                 continue
22             }
23             
24             result = min(ends[key]! - starts[key]! + 1, result)
25         }        
26 
27         return result
28     }
29 }

240ms

 1 class Solution {
 2     func findShortestSubArray(_ nums: [Int]) -> Int {
 3         var dict = [Int: [Int]]()
 4         var frequency = Dictionary( nums.map{ ($0, 1) }, uniquingKeysWith: +)
 5         var degree = 0
 6         for (key, value) in frequency {
 7             degree = max(value, degree)
 8         }
 9         var degreeItemArray = Set<Int>()
10         for (key, value) in frequency {
11             if value == degree {
12                 degreeItemArray.insert(key)
13             }
14         }
15         for i in 0..<nums.count {
16             guard degreeItemArray.contains(nums[i]) else {
17                 continue
18             }
19             dict[nums[i]] = dict[nums[i]] ?? [i, i]
20             var items = dict[nums[i]]!
21             if i > items[1] {
22                 items[1] = i
23             }
24             dict[nums[i]] = items
25         }
26         var result = Int.max
27         for (key, value) in dict {
28             result = min(result, value[1] - value[0] + 1)
29         }
30         return result
31     }
32 }

264ms

 1 class ItemInfo {
 2     let value: Int
 3     var count: Int
 4     var startIndex: Int
 5     var endIndex: Int
 6     
 7     var length: Int {
 8         return self.endIndex - self.startIndex + 1
 9     }
10     
11     init(value: Int, at index: Int) {
12         self.value = value
13         self.count = 1
14         self.startIndex = index
15         self.endIndex = index
16     }
17     
18     func addItem(at index: Int) -> Self {
19         self.count += 1
20         self.startIndex = min(startIndex, index)
21         self.endIndex = max(endIndex, index)
22         
23         return self
24     }
25 }
26 
27 class Solution {
28     func findShortestSubArray(_ nums: [Int]) -> Int {
29         guard nums.count > 1 else {
30             return nums.count
31         }
32         
33         var info: [Int: ItemInfo] = [:]
34         
35         for (index, num) in nums.enumerated() {
36             if let currentInfo = info[num] {
37                 info[num] = currentInfo.addItem(at: index)
38             } else {
39                 info[num] = ItemInfo(value: num, at: index)
40             }
41         }
42         
43         if let max = info.max(by: { (arg1, arg2) -> Bool in
44             return arg1.value.count < arg2.value.count || (arg1.value.count == arg2.value.count && arg1.value.length > arg2.value.length)
45         }) {
46             return max.value.length
47         } else {
48             return -1
49         }
50     }
51 }

284ms

 1 class Solution {
 2     func findShortestSubArray(_ nums: [Int]) -> Int {
 3         var firstIndexMap = [Int: Int]()
 4         var lastIndexMap = [Int: Int]()
 5         var countMap = [Int: Int]()
 6 
 7         // Find the "degree" (most frequent element count)
 8         var maxCount = 0
 9         for (i, num) in nums.enumerated() {
10             if let count = countMap[num] {
11                 maxCount = max(maxCount, count + 1)
12                 countMap[num] = count + 1
13                 lastIndexMap[num] = i
14             } else {
15                 countMap[num] = 1
16                 firstIndexMap[num] = i
17             }
18             
19             maxCount = max(maxCount, countMap[num]!)
20         }
21         
22         guard maxCount > 1 else { return maxCount }
23 
24         let maxDict = countMap.filter { k, v in v == maxCount }
25 
26         var lengthsDict = [Int: Int]()
27         for (key, _) in maxDict {
28             lengthsDict[key] = lastIndexMap[key]! - firstIndexMap[key]! + 1
29         }
30 
31         let minValue = [Int](lengthsDict.values).min() ?? 0
32 
33         return minValue
34     }
35 }

440ms

 1 class Solution {
 2     func findShortestSubArray(_ nums: [Int]) -> Int {
 3         
 4         if nums.count <= 1 {
 5             return nums.count
 6         }
 7         
 8         var dict = [Int: [String: Int]]()
 9         
10         for i in 0..<nums.count {
11             
12             let value = nums[i]
13             
14             if dict[value] == nil {
15                 dict[value] = [
16                     "start": i,
17                     "end": i,
18                     "count": 1
19                 ]
20             } else {
21                 dict[value]!["end"] = i
22                 dict[value]!["count"] = dict[value]!["count"]! + 1
23             }
24         }
25         
26         var count = Int.min
27         var degree = Int.max
28         
29         for key in dict.keys {
30             
31             let d = dict[key]
32             
33             guard let c = d!["count"] else {
34                 continue
35             }
36             
37             if c < count {
38                 continue
39             }
40             
41             guard let s = d!["start"] else {
42                 continue
43             }
44             
45             guard let e = d!["end"] else {
46                 continue
47             }
48             
49             if c > count {
50                 degree = e - s + 1
51             } else {
52                 degree = min(degree, e - s + 1)
53             }
54             
55             count = max(count, c)
56         }
57         
58         return degree == Int.max ? 1 : degree
59     }
60 }