首页 > itarticle > 算法笔记: 力扣#697 数组的度

算法笔记: 力扣#697 数组的度

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

class :
    def findShortestSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        counter = dict()
        min_ix = dict()
        max_ix = dict()
        for ix, num in enumerate(nums):
            if num in counter:
                counter[num] += 1
            else:
                counter[num] = 1
                min_ix[num] = ix
            max_ix[num] = ix
        max_freq = max(counter.values())
        return min(max_ix[num]-min_ix[num]+1 for num, freq in counter.items() if freq==max_freq)

Java 实现

class  {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> counter = new HashMap<>();
        Map<Integer, Integer> minIx = new HashMap<>();
        Map<Integer, Integer> maxIx = new HashMap<>();
        
        for(int i = 0; i < nums.length; i++){
            int num = nums[i];
            if(counter.containsKey(num)){
                counter.put(num, counter.get(num)+1);
            }else{
                counter.put(num, 1);
                minIx.put(num, i);
            }
            maxIx.put(num, i);
        }
        int maxFreq = Collections.max(counter.values());
        int ans = nums.length;
        for(int num : counter.keySet()){
            if(counter.get(num) == maxFreq){
                int temp = maxIx.get(num)-minIx.get(num)+1;
                ans = ans < temp ? ans : temp;
            }
        }
        return ans;
    }
}

时间复杂度

空间复杂度

链接

697. Degree of an Array
697. 数组的度
 (English version) Algorithm Notes: Leetcode#697 Degree of an Array