697. Degree of an Array

LintCode Array

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.

分析

数组的度。最直接的方法：利用哈希表找到数组的度，然后找到度的对应数字，寻找这些数字的长度的最小值。

public int findShortestSubArray(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    // map中的键是nums中的数字，值是在nums中出现的位置
    Map<Integer, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        if (!map.containsKey(num)) map.put(num, new ArrayList<>());
        map.get(num).add(i);
    }

    // 计算数组nums的degree
    int degree = 0;
    for (int num : map.keySet())
        degree = Math.max(degree, map.get(num).size());

    // 计算在nums中达到最大degree的数字
    List<Integer> degreeList = new ArrayList<>();
    for (int num : map.keySet())
        if (degree == map.get(num).size()) degreeList.add(num);       

    // 计算最小长度
    int minLength = nums.length;
    for (int num : degreeList) {
        List<Integer> positions = map.get(num);
        Collections.sort(positions);
        int length = positions.get(positions.size() - 1) 
                    - positions.get(0) + 1;
        if (length < minLength) minLength = length;
    }
    return minLength;   
}