This is the fourth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

If you have more than one mode, take the one with the shortest interval length

— Leetcode

preface

Hello, everyone. I’m One.

Confused algorithm, rarely confused

Question

697. Degree of array

Difficulty: Easy

Given a nums array of non-empty integers containing only non-negative numbers, the degree of the array is defined as the maximum number of occurrences of any element in the set of exponents.

Your task is to find the shortest contiguous subarray in NUMS that has the same degree as NUMS and return its length.

Example 1:

Input: [1, 2, 2, 3, 1] Output: 2 Continuous subarray inside with the same degree as follows: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] continuous subarray shortest length is 2 [2, 2], so back to 2.Copy the code

Example 2:

Input: [1,2,2,3,1,4,2] output: 6Copy the code

Tip:

Nums. length ranges from 1 to 50,000. Nums [I] is an integer in the range 0 to 49,999.

Solution

The degree is the number that appears the most, the mode, which is easier to understand,

The harder question is what does it ask? — The length of the shortest subarray with the same degree

The difference between the first and last position of the number of degrees

Divide the topic into two parts:

  • Degree, you can use the hash table to calculate times
  • Seek difference, can record the position coordinate of each number

Synthesis:

  • Key: digital
  • Value: [number of times, first occurrence position, last occurrence position]

Code

All LeetCode codes have been synchronized to Github

Welcome to star

/ * * *@authorA coding * /
class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, int[]> map = new HashMap<Integer, int[] > ();int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (map.containsKey(nums[i])) {
              // The number of occurrences is increased by one
                map.get(nums[i])[0] + +;// Record the end position
                map.get(nums[i])[2] = i;
            } else {
              // First occurrence, record the initial position
                map.put(nums[i], new int[] {1, i, i}); }}int maxNum = 0, minLen = 0;
      // Walk through the map to find the smallest difference of the largest degree
        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
            int[] arr = entry.getValue();
            if (maxNum < arr[0]) {
                maxNum = arr[0];
                minLen = arr[2] - arr[1] + 1;
            } else if (maxNum == arr[0]) {
                if (minLen > arr[2] - arr[1] + 1) {
                    minLen = arr[2] - arr[1] + 1; }}}returnminLen; }}Copy the code

Result

Complexity analysis

  • Time complexity: O(N)

Finally, if the article is helpful to you.

Remember to give the article a thumbs up!

Also give a point attention!