[697][Degree_of_an_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. 顧名思義，找到陣列裡重複出現次數最多的數，把這個數最一開始出現到最後出現形成子陣列，回傳最小長度的子陣列即可。

範例

Input: nums = [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.

思路： 選擇用HashMap先去把陣列中每個數當key，該數出現的次數當value存起來，找出HashMap用value排序最大的數(亦即該陣列出現最多次處的數)，然後去跑function findShortestDegree() ->找出該數的子陣列長度，回傳存進ArrayList(用ArrayList裝的用處是怕有多個重複次數一樣的數)，最後排序ArrayList拿取最小的即為答案

解題：

class Solution {
    public int findShortestSubArray(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(Integer i : nums){
            if(map.containsKey(i)){
                map.put(i,map.get(i)+1);
            }else{
                map.put(i,1);
            }
        }
        int maxValueInMap=(Collections.max(map.values())); //出現最多次數
        List<Integer> maxTimeNumberList = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue()==maxValueInMap) {
                maxTimeNumberList.add(findShortestDegree(nums,entry.getKey()));
            }
        }
        Collections.sort(maxTimeNumberList);
        return maxTimeNumberList.get(0);
    }

    //算出該數子陣列長度
    public int findShortestDegree(int[] nums,int target){
        int frontIndex = 0;
        int backIndex = 0;
        int size = nums.length;
        for(int i=0; i<nums.length; i++){
            if(target == nums[i]){
                frontIndex = i;
                break;
            }
        }
        for(int i=size-1; i>=0; i--){
            if(target == nums[i]){
                backIndex = i;
                break;
            }
        }
        return backIndex-frontIndex+1;
    }
}

Barney30818 / LeetPractice

[697][Degree_of_an_Array] #3