leetcode 697

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

给定非空整数nums的非空数组，该数组的度数被定义为其任何一个元素的最大频率。

你的任务是找到num的（连续的）子阵列的最小可能长度，其与nums具有相同的度数。

例1：
输入：[1,2,2,3,1]
输出：2
说明：
输入数组的度数为2，因为元素1和2都出现两次。
在具有相同程度的子阵列中：
[1,2,2,3,1]，[1,2,2,3]，[2,2,3,1]，[1,2,2]，[2,2,3]，[2] ，2]
最短的长度是2.所以返回2。
例2：
输入：[1,2,2,3,1,4,2]
输出：6

class Solution {

	public int findShortestSubArray(int[] nums) {

		int maxcount = 1;

		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

		for (int i : nums) {

			if (hm.containsKey(i)) {

				hm.put(i, hm.get(i) + 1);

				if (maxcount < hm.get(i)) {

					maxcount = hm.get(i);

				}

			} else {

				hm.put(i, 1);

			}

		}

		Set<Integer> set = hm.keySet();

		int minlength = Integer.MAX_VALUE;

		for (int s : set) {

			int temp = Integer.MAX_VALUE;

			if (hm.get(s) == maxcount) {

				int i = 0, j = nums.length - 1;

				while (nums[i] != s && i < j)

					i++;

				while (nums[j] != s && i < j)

					j--;

				temp = j - i + 1;

			}

			minlength = Math.min(temp, minlength);

		}

		return minlength;

	}

}

巴特西

leetcode 697

最新文章

热门文章