Welcome to Subscribe On Youtube
697. Degree of an Array
Level
Easy
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
Note:
nums.length
will be between 1 and 50,000.nums[i]
will be an integer between 0 and 49,999.
Solution
First get each number’s frequency in array nums
. Next obtain the numbers with the maximum frequency. Then for each number with the maximum frequency, obtain the first occurrence minIndex
and the last occurrence maxIndex
of the number, and the subarray with this number has length maxIndex - minIndex + 1
. Finally, return the minimum possible length among the subarrays of each number with maximum frequency.
-
public class Degree_of_an_Array { public static void main(String[] args) { Degree_of_an_Array out = new Degree_of_an_Array(); Solution s = out.new Solution(); System.out.println(s.findShortestSubArray(new int[]{1,2,2,3,1})); } // time: O(N) // space: O(N) class Solution { public int findShortestSubArray(int[] nums) { if (nums == null || nums.length == 0) { return 0; } Map<Integer, Integer> firstIndex = new HashMap<>(); Map<Integer, Integer> lastIndex = new HashMap<>(); Map<Integer, Integer> count = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int x = nums[i]; firstIndex.putIfAbsent(x, i); // only update first time lastIndex.put(x, i); count.put(x, count.getOrDefault(x, 0) + 1); } int result = nums.length; int degree = Collections.max(count.values()); for (int x: count.keySet()) { if (count.get(x) == degree) { result = Math.min(result, lastIndex.get(x) - firstIndex.get(x) + 1); } } return result; } } } ############ class Solution { public int findShortestSubArray(int[] nums) { Map<Integer, Integer> cnt = new HashMap<>(); Map<Integer, Integer> left = new HashMap<>(); Map<Integer, Integer> right = new HashMap<>(); int degree = 0; for (int i = 0; i < nums.length; ++i) { int v = nums[i]; cnt.put(v, cnt.getOrDefault(v, 0) + 1); degree = Math.max(degree, cnt.get(v)); if (!left.containsKey(v)) { left.put(v, i); } right.put(v, i); } int ans = 1000000; for (int v : nums) { if (cnt.get(v) == degree) { int t = right.get(v) - left.get(v) + 1; if (ans > t) { ans = t; } } } return ans; } }
-
// OJ: https://leetcode.com/problems/degree-of-an-array/ // Time: O(N) // Space: O(N) class Solution { public: int findShortestSubArray(vector<int>& nums) { unordered_map<int, int> cnt, left, right; int deg = 0, ans = INT_MAX; for (int i = 0; i < nums.size(); ++i) { int n = nums[i]; cnt[n]++; if (cnt[n] > deg) deg = cnt[n]; if (cnt[n] == 1) left[n] = i; right[n] = i; } for (auto p : cnt) { if (p.second != deg) continue; ans = min(ans, right[p.first] - left[p.first] + 1); } return ans; } };
-
class Solution: def findShortestSubArray(self, nums: List[int]) -> int: cnt = Counter(nums) degree = cnt.most_common()[0][1] left, right = {}, {} for i, v in enumerate(nums): if v not in left: left[v] = i right[v] = i ans = inf for v in nums: if cnt[v] == degree: t = right[v] - left[v] + 1 if ans > t: ans = t return ans ############ import collections class Solution(object): def findShortestSubArray(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) == len(set(nums)): return 1 counter = collections.Counter(nums) degree_num = counter.most_common(1)[0] most_numbers = [num for num in counter if counter[num] == degree_num[1]] scale = 100000000 for most_number in most_numbers: appear = [i for i,num in enumerate(nums) if num == most_number] appear_scale = max(appear) - min(appear) + 1 if appear_scale < scale: scale = appear_scale return scale
-
func findShortestSubArray(nums []int) (ans int) { ans = 50000 numsMap := make(map[int]int, len(nums)) for _, num := range nums { numsMap[num]++ } var maxDegree int for _, num := range numsMap { maxDegree = max(num, maxDegree) } degreeNums := getMaxDegreeElem(maxDegree, numsMap) for _, num := range degreeNums { f := findSubArray(num, nums) ans = min(ans, f) } return } func findSubArray(target int, nums []int) int { start := getStartIdx(target, nums) end := getEndIdx(target, nums) return (end - start) + 1 } func getStartIdx(target int, nums []int) (start int) { for idx, num := range nums { if num == target { start = idx break } } return start } func getEndIdx(target int, nums []int) (end int) { for i := len(nums) - 1; i > 0; i-- { if nums[i] == target { end = i break } } return } func getMaxDegreeElem(maxDegree int, numsMap map[int]int) []int { var ans []int for key, value := range numsMap { if value == maxDegree { ans = append(ans, key) } } return ans } func min(a, b int) int { if a > b { return b } return a } func max(a, b int) int { if a > b { return a } return b }
-
class Solution { public int findShortestSubArray(int[] nums) { Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>(); int maxFrequency = 0; for (int num : nums) { int frequency = frequencyMap.getOrDefault(num, 0); frequency++; maxFrequency = Math.max(maxFrequency, frequency); frequencyMap.put(num, frequency); } Set<Integer> maxFrequencySet = new HashSet<Integer>(); Set<Integer> keySet = frequencyMap.keySet(); for (int num : keySet) { int frequency = frequencyMap.getOrDefault(num, 0); if (frequency == maxFrequency) maxFrequencySet.add(num); } Map<Integer, List<Integer>> numIndicesMap = new HashMap<Integer, List<Integer>>(); int length = nums.length; for (int i = 0; i < length; i++) { int num = nums[i]; if (maxFrequencySet.contains(num)) { List<Integer> indices = numIndicesMap.getOrDefault(num, new ArrayList<Integer>()); indices.add(i); numIndicesMap.put(num, indices); } } int minLength = length; for (int num : maxFrequencySet) { List<Integer> indices = numIndicesMap.getOrDefault(num, new ArrayList<Integer>()); int size = indices.size(); if (size > 0) { int minIndex = indices.get(0), maxIndex = indices.get(size - 1); minLength = Math.min(minLength, maxIndex - minIndex + 1); } } return minLength; } } ############ class Solution { public int findShortestSubArray(int[] nums) { Map<Integer, Integer> cnt = new HashMap<>(); Map<Integer, Integer> left = new HashMap<>(); Map<Integer, Integer> right = new HashMap<>(); int degree = 0; for (int i = 0; i < nums.length; ++i) { int v = nums[i]; cnt.put(v, cnt.getOrDefault(v, 0) + 1); degree = Math.max(degree, cnt.get(v)); if (!left.containsKey(v)) { left.put(v, i); } right.put(v, i); } int ans = 1000000; for (int v : nums) { if (cnt.get(v) == degree) { int t = right.get(v) - left.get(v) + 1; if (ans > t) { ans = t; } } } return ans; } }
-
// OJ: https://leetcode.com/problems/degree-of-an-array/ // Time: O(N) // Space: O(N) class Solution { public: int findShortestSubArray(vector<int>& nums) { unordered_map<int, int> cnt, left, right; int deg = 0, ans = INT_MAX; for (int i = 0; i < nums.size(); ++i) { int n = nums[i]; cnt[n]++; if (cnt[n] > deg) deg = cnt[n]; if (cnt[n] == 1) left[n] = i; right[n] = i; } for (auto p : cnt) { if (p.second != deg) continue; ans = min(ans, right[p.first] - left[p.first] + 1); } return ans; } };
-
class Solution: def findShortestSubArray(self, nums: List[int]) -> int: cnt = Counter(nums) degree = cnt.most_common()[0][1] left, right = {}, {} for i, v in enumerate(nums): if v not in left: left[v] = i right[v] = i ans = inf for v in nums: if cnt[v] == degree: t = right[v] - left[v] + 1 if ans > t: ans = t return ans ############ import collections class Solution(object): def findShortestSubArray(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) == len(set(nums)): return 1 counter = collections.Counter(nums) degree_num = counter.most_common(1)[0] most_numbers = [num for num in counter if counter[num] == degree_num[1]] scale = 100000000 for most_number in most_numbers: appear = [i for i,num in enumerate(nums) if num == most_number] appear_scale = max(appear) - min(appear) + 1 if appear_scale < scale: scale = appear_scale return scale
-
func findShortestSubArray(nums []int) (ans int) { ans = 50000 numsMap := make(map[int]int, len(nums)) for _, num := range nums { numsMap[num]++ } var maxDegree int for _, num := range numsMap { maxDegree = max(num, maxDegree) } degreeNums := getMaxDegreeElem(maxDegree, numsMap) for _, num := range degreeNums { f := findSubArray(num, nums) ans = min(ans, f) } return } func findSubArray(target int, nums []int) int { start := getStartIdx(target, nums) end := getEndIdx(target, nums) return (end - start) + 1 } func getStartIdx(target int, nums []int) (start int) { for idx, num := range nums { if num == target { start = idx break } } return start } func getEndIdx(target int, nums []int) (end int) { for i := len(nums) - 1; i > 0; i-- { if nums[i] == target { end = i break } } return } func getMaxDegreeElem(maxDegree int, numsMap map[int]int) []int { var ans []int for key, value := range numsMap { if value == maxDegree { ans = append(ans, key) } } return ans } func min(a, b int) int { if a > b { return b } return a } func max(a, b int) int { if a > b { return a } return b }