LeetCode 697. Degree of an Array

发表于 | 分类于 ，
字数统计： 4.4k | 阅读时长≈ 0:04

LeetCode 697. Degree of an Array

Description:

Given a non-empty array of non-negative integers nums, the degree of 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

解法一：

先用哈希表hash记录每一个数字出现的次数，找出最高频率maxFreq
然后从哈希表中找出最高频率的数字
计算最高频率的数字在原数组中出现的左右边界
左右边界的间隔+1即为结果

例如：输入vector为1，2，2，3，1，4，2；输出结果为6
根据上述解法得到hash过程如下：
hash[1]=1, maxFreq=1
hash[2]=1, maxFreq=1
hash[2]=2, maxFreq=2
hash[3]=1, maxFreq=2
hash[1]=2, maxFreq=2
hash[4]=1, maxFreq=2
hash[2]=3, maxFreq=3
因此我们可以看到hash[nums[i]] == maxFreq时，nums[i]即为出现频率最高的数字。
接下来就是找最高频率数字的左右边界了，见代码解释即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
input:
1 2 2 3 1 4 2
output:
6
 */
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
	int findShortestSubArray(vector<int>& nums) {
		unordered_map<int, int> hash;// 哈希表记录每个数字出现的次数
		int maxFreq = 0;
		for (int i = 0; i < nums.size(); i++) {
			hash[nums[i]]++;
			maxFreq = max(hash[nums[i]], maxFreq);// 找出最高频率
		}
		if (maxFreq == 1) return 1;

		vector<int> maxFreqNum;// 找出最高频率的数字
		for (auto m : hash) {
			if (m.second == maxFreq) {
				maxFreqNum.push_back(m.first);
			}
		}

		int maxLen = nums.size();// 最大长度结果
		for (int i = 0; i < maxFreqNum.size(); i++) {
			int minIndex = -1;// 找出最高频率数字在数组中最左边的下标
			int maxIndex = -1;// 找出最高频率数字在数组中最右边的下标
			int freq = maxFreq;
			for (int j = 0; j < nums.size() && freq > 0; j++) {
				if (nums[j] == maxFreqNum[i]) {
					freq--;
					if (minIndex == -1) minIndex = j;// minIndex等于-1时，即为最左边位置
					if (freq == 0) maxIndex = j;// freq等于0时，即为最右边位置
				}
			}
			// 更新最大长度结果
			if (maxIndex - minIndex + 1 < maxLen) {
				maxLen = maxIndex - minIndex + 1;
			}
		}
		
		return maxLen;
	}
};
int main() {
	Solution s;
	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	cout << s.findShortestSubArray(nums) << endl;
	return 0;
}

解法二：

采用三个哈希表，一个和解法一一样，记录每个数字出现的次数，一个是每个数字出现的最左边位置，一个是每个数字出现的最右边位置。
由于采用了以空间换时间的方法，故大大降低了时间复杂度。

例如：输入vector为1，2，2，3，1，4，2；输出结果为6
根据上述解法得到hash过程如下：
hash[1]=1, maxFreq=1, hash_left[1]=0, hash_right[1]=0
hash[2]=1, maxFreq=1, hash_left[2]=1, hash_right[2]=1
hash[2]=2, maxFreq=2, hash_left[2]=1, hash_right[2]=2
hash[3]=1, maxFreq=2, hash_left[3]=3, hash_right[3]=3
hash[1]=2, maxFreq=2, hash_left[1]=0, hash_right[1]=4
hash[4]=1, maxFreq=2, hash_left[4]=5, hash_right[4]=5
hash[2]=3, maxFreq=3, hash_left[2]=1, hash_right[2]=6
因此我们可以看到hash[nums[i]] == maxFreq时，nums[i]即为出现频率最高的数字。
接下来就是找最高频率数字的左右边界了，直接利用hash_right[nums[i]] - hash_left[nums[i]] + 1即可

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
input:
1 2 2 3 1 4 2
output:
6
 */
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
	int findShortestSubArray(vector<int>& nums) {
		unordered_map<int, int> hash;// 哈希表记录每个数字出现的次数
		unordered_map<int, int> hash_left;// 哈希表维护每个数组出现的最左位置
		unordered_map<int, int> hash_right;// 哈希表维护每个数组出现的最右位置

		int maxFreq = 0;
		for (int i = 0; i < nums.size(); i++) {
			hash[nums[i]]++;
			maxFreq = max(hash[nums[i]], maxFreq);// 找出最高频率

			if (hash_left.find(nums[i]) == hash_left.end()) {// 为真，即表示该数字还没出现
				hash_left[nums[i]] = i;
			}
			hash_right[nums[i]] = i;
		}
		if (maxFreq == 1) return 1;

		int maxLen = nums.size();
		for (auto m : hash) {
			if (m.second == maxFreq) {
				maxLen = min(maxLen, hash_right[m.first] - hash_left[m.first] + 1);
			}
		}
		
		return maxLen;
	}
};
int main() {
	Solution s;
	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	cout << s.findShortestSubArray(nums) << endl;
	return 0;
}
------本文结束感谢阅读------