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:

1
2
3
4
5
6
7
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:

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

分析

题目大意是，有一个非空非负的 int 类型的数组，定义 degree 为一个数组中所有元素出现频率的最大值，找出这个数组有相同 degree 的子集的长度的最小值。

思路是定义一个 pos 数组，记录每个元素第一次出现时的位置，定义一个 frequncy 数组，记录每个元素出现的频率，遍历数组，如果当前元素出现的频率大于已经记录的最大频率，那么记录这个距离，如果当前元素出现的频率等于已经记录的最大频率，那么最小的长度等于当前距离和已经记录的最小距离的较小者。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int findShortestSubArray(int[] nums) {
        int minLength = 1;
        int currentLength = 0;
        int maxFrequency = 0;
        int[] frequency = new int[50001];
        int[] pos = new int[50001];
        
        for (int i = 0; i < nums.length; i++) {
            if (pos[nums[i]] == 0) {
                pos[nums[i]] = i+1;
            } else {
                frequency[nums[i]]++;
                currentLength = i - pos[nums[i]] + 2;
                if (frequency[nums[i]] > maxFrequency) {
                    maxFrequency = frequency[nums[i]];
                    minLength = currentLength;
                } else if (frequency[nums[i]] == maxFrequency){
                    minLength = currentLength < minLength ? currentLength: minLength;
                }
            }
        }
        return minLength;
    }
}

相关问题

(M) Maximum Subarray

题目来源