leetcode 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.

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.

我的答案

import java.util.*;

public class DegreeOfArray {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String num = sc.nextLine();
        int[] nums = stringToInts(num);//把字符串变成数列
        Map<Integer,Integer> count = count(nums);//统计数列中各种字符出现的次数
        int degree = findFrequency(count);//找到数列的最高频率
        //System.out.println("degree="+degree);
        int shortestSubarr = findShortestSubarr(nums,degree,count);//统计最高频率的数字的子序列长度
        System.out.println(shortestSubarr);

    }
    public static int[] stringToInts(String nums){
        String num[] = nums.replace("[","").replaceAll("]","").split(",");
        int[] n = new int[num.length];
        for(int i = 0;i<num.length;i++) {
            n[i] = Integer.valueOf(num[i]).intValue();
            //System.out.println(n[i]+" "+i);
        }
        return n;
    }
    public static Map<Integer,Integer> count(int[] nums) {
        Map<Integer,Integer> count = new HashMap<>();
        for (int item : nums){
            if (count.containsKey(item)) {
                count.put(item, count.get(item) + 1);
            }else {
                count.put(item, 1);
            }
        }
        //System.out.println("count="+count);
        return count;
    }
    public static int findFrequency(Map count){
        int value[] = new int[count.size()];
        int i=0;
        Iterator<Integer> iter = count.values().iterator();
        while (iter.hasNext()) {
            value[i] = iter.next();
            i++;
        }
        Arrays.sort(value);
        return value[value.length-1];
    }
    public static int findShortestSubarr(int[] nums,int degree,Map<Integer,Integer> count){
        Map<Integer,Integer> subarrMap = new HashMap<>();
        Iterator<Integer> iter = count.keySet().iterator();
        for (Integer key : count.keySet()){
            if(count.get(key)==degree){
                int formmer = 0,latter = 0;
                for (int i=0;i<nums.length;i++){
                    if (nums[i]==key){
                        formmer=i;
                        break;
                    }
                }
                for(int i=nums.length-1;i>0;i--){
                    if(nums[i]==key){
                        latter=i;
                        break;
                    }
                }
                //System.out.println("FORMMER="+formmer+" latter="+latter);
                subarrMap.put(key,latter-formmer+1);
            }
        }
        int shortestSubarr = 50000;
        for (Integer key : subarrMap.keySet()){
            if (shortestSubarr > subarrMap.get(key)) {
                shortestSubarr = subarrMap.get(key);
            }
        }
        return shortestSubarr;
    }
}

运行时间最短的答案

class Solution {

    public int findShortestSubArray(int[] nums) {

        Map<Integer, Integer> left = new HashMap(),

            right = new HashMap(), count = new HashMap(); 
        //原来这里可以这样定义

        for (int i = 0; i < nums.length; i++) {

            int x = nums[i];

            if (left.get(x) == null) left.put(x, i);
            //原来这样看第一次出现的位置

            right.put(x, i);//这样看最后一次出现的位置

            count.put(x, count.getOrDefault(x, 0) + 1);//getOrDefault方法
                                                       //用这种方法数每个元素出现多少次

        }

        int ans = nums.length;

        int degree = Collections.max(count.values());//用Collections.max找value最大值

        for (int x: count.keySet()) {

            if (count.get(x) == degree) {

                ans = Math.min(ans, right.get(x) - left.get(x) + 1);//用这种方法找最短的子序列长度

            }

        }

        return ans;

    }

}

巴特西

leetcode 697. Degree of an Array

最新文章

热门文章