FanluLeetcode/src/array/DegreeOfAnArray.java at master · Fanlu91/FanluLeetcode · GitHub

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package array;

// Source : https://leetcode.com/problems/degree-of-an-array/
// Id     : 697
// Author : Fanlu Hai | https://github.com/Fanlu91/FanluLeetcode
// Date   : 2019-06-11
// Topic  : Array
// Level  : Easy
// Other  :
// Tips   :
// Result : 100.00% 54.88%

import java.util.HashMap;
import java.util.Map;

public class DegreeOfAnArray {

    // 61.95% 21 ms 97.83%
    public int findShortestSubArrayOrigin(int[] nums) {
        Map<Integer, Integer> degreeMap = new HashMap<>();
        Map<Integer, Integer> startIndexMap = new HashMap<>();
        Map<Integer, Integer> endIndexMap = new HashMap<>();
        int arrayDegree = 1;
        int tmpDegree;
        for (int i = 0; i < nums.length; i++) {
            if (degreeMap.containsKey(nums[i])) {
                tmpDegree = degreeMap.get(nums[i]) + 1;
                if (tmpDegree > arrayDegree)
                    arrayDegree = tmpDegree;
                degreeMap.put(nums[i], tmpDegree);
                endIndexMap.put(nums[i], i);
            } else {
                degreeMap.put(nums[i], 1);
                startIndexMap.put(nums[i], i);
            }
        }

        if (endIndexMap.isEmpty())
            return 1;

        int smallestLength = 50000; // according to condition provided.
        int tmpLength = 0;
        for (int key : endIndexMap.keySet()) {
            if (arrayDegree == degreeMap.get(key)) {
//                System.out.println("key " + key + " end " + endIndexMap + " start " + startIndexMap);
                tmpLength = endIndexMap.get(key) - startIndexMap.get(key);
                if (tmpLength < smallestLength)
                    smallestLength = tmpLength;
            }
        }
        return smallestLength + 1;
    }

    // 93.06% 10 ms  94.04%
    public int findShortestSubArrayImproved(int[] nums) {

        HashMap<Integer, int[]> intToFreqInfo = new HashMap<>();

        int maxDegree = 1;
        for (int i = 0; i < nums.length; ++i) {
            if (!intToFreqInfo.containsKey(nums[i])) {
                intToFreqInfo.put(nums[i], new int[]{1, i, i});
            } else {
                int[] freqInfo = intToFreqInfo.get(nums[i]);
                maxDegree = Math.max(maxDegree, ++freqInfo[0]);
                freqInfo[2] = i;
            }
        }

        int smallestLength = 50000;
        for (int[] freqInfo : intToFreqInfo.values()) {
            if (freqInfo[0] == maxDegree) {
                smallestLength = Math.min(smallestLength, freqInfo[2] - freqInfo[1]);
            }
        }

        return smallestLength + 1;
    }

    // learned from leetcode submission
    // 1.use array to replace hashmap
    // 2.update min on the go instead of storing head and compute later. Really nice logic.
    // 100.00% 54.88%
    public int findShortestSubArray(int[] nums) {
        int[] head = new int[50001];
        int[] degree = new int[50001];

        for (int i = 0; i < 50000; i++)
            head[i] = -1;

        int min = nums.length, max = 1;
        for (int i = 0; i < nums.length; i++) {
            if (head[nums[i]] == -1)
                head[nums[i]] = i;

            degree[nums[i]]++;

            if (degree[nums[i]] > max) {
                max = degree[nums[i]];
                // this step is the key
                min = i - head[nums[i]] + 1;

            } else if (degree[nums[i]] == max && min > i - head[nums[i]] + 1)
                min = i - head[nums[i]] + 1;
        }
        return min;
    }

}