[LeetCode] 697. Degree of an Array

轉自LeetCode

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>

想法如下

• 所有符合條件的subarray，都至少必須包含出現最多次的數字。因此，去紀錄每個數字的 leftmost index 和 rightmost index，以及出現的次數。當某個數字符合條件，最短長度就會是 rightmost index - leftmost index + 1

• 因為可能有多個數字的都符合條件，所以必須在其中找到最短的

code 如下

Java(參考解答)

	class Solution {
	public int findShortestSubArray(int[] nums) {
	HashMap<Integer, Integer> leftIdxMap = new HashMap<>();
	HashMap<Integer, Integer> rightIdxMap = new HashMap<>();
	HashMap<Integer, Integer> cntMap = new HashMap<>();
	int num;
	for(int i = 0; i < nums.length; i++) {
	num = nums[i];
	if(!leftIdxMap.containsKey(num)) {
	leftIdxMap.put(num, i);
	}
	rightIdxMap.put(num, i);
	cntMap.put(num, cntMap.getOrDefault(num, 0) + 1);
	}
	int ans = Integer.MAX_VALUE;
	final int degree = Collections.max(cntMap.values());
	for(int k : cntMap.keySet()) {
	if(cntMap.get(k) == degree) {
	ans = Math.min(ans, rightIdxMap.get(k) - leftIdxMap.get(k) + 1);
	}
	}
	return ans;
	}
	}

view raw findShortestSubArray.java hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun findShortestSubArray(nums: IntArray): Int {
	val leftIndexMap = mutableMapOf<Int,Int>()
	val rightIndexMap = mutableMapOf<Int,Int>()
	val degreeMap = mutableMapOf<Int,Int>()
	var maxDegree = 0
	for(i in nums.indices) {
	if(leftIndexMap[nums[i]] == null) {
	leftIndexMap[nums[i]] = i
	}
	rightIndexMap[nums[i]] = i
	degreeMap[nums[i]] = degreeMap[nums[i]]?.let{it+1} ?: 1
	maxDegree = Math.max(maxDegree, degreeMap[nums[i]]!!)
	}
	val degreeNums = degreeMap.asSequence()
	.filter { it.value == maxDegree }
	.map { it.key }
	var ans = Int.MAX_VALUE
	for(n in degreeNums) {
	ans = Math.min(ans, rightIndexMap[n]!! - leftIndexMap[n]!! + 1)
	}
	return ans
	}
	}

view raw degree_of_array.kt hosted with ❤ by GitHub