This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is the degree of the 697. Array on LeetCode, the difficulty is simple.

Tag: Hash table

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.

An array of count

Since the range of known values is [0, 49999].

We can count the number of occurrences of each value using the array CNT, with the arrays first and last recording the “first” and “last” subscripts of each value.

At the same time, the maximum word frequency is Max.

The array is then iterated again, calculating the length of values that satisfy the word frequency of Max.

class Solution {
    int N = 50009;
    public int findShortestSubArray(int[] nums) {
        int n = nums.length;
        int[] cnt = new int[N];
        int[] first = new int[N], last = new int[N];
        Arrays.fill(first, -1);
        int max = 0;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            max = Math.max(max, ++cnt[t]);
            if (first[t] == -1) first[t] = i;
            last[t] = i;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            if (cnt[t] == max) ans = Math.min(ans, last[t] - first[t] + 1);
        }
        returnans; }}Copy the code
  • Time complexity: Constant number of scans of the array. The complexity is O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Hash table counting

Similarly, instead of using static arrays, we can use hash tables to count.

class Solution {
    public int findShortestSubArray(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> cnt = new HashMap<>();
        Map<Integer, Integer> first = new HashMap<>(), last = new HashMap<>();
        int max = 0;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            cnt.put(t, cnt.getOrDefault(t, 0) + 1);
            max = Math.max(max, cnt.get(t));
            if(! first.containsKey(t)) first.put(t, i); last.put(t, i); }int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            if (cnt.get(t) == max) {
                ans = Math.min(ans, last.get(t) - first.get(t) + 1); }}returnans; }}Copy the code
  • Time complexity: Constant number of scans of the array. The complexity is O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

conclusion

We know that hash table = hash function + array, due to the time spent calculating hash functions (in Java, it involves automatic boxing/unboxing first, then right-shifting the hashCode of the object to xor, and finally calculating the subscript of the hash bucket), and the overhead of dealing with hash conflicts.

It’s certainly not as efficient as counting with our static array.

Therefore, I recommend using arrays rather than hash tables for computations where the range of values is fixed and not too large (up to 10610^6106).

The last

This is the No.697 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks, we will finish all the topics without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.