DegreeOfAnArray [source code]

public class DegreeOfAnArray {
static
/******************************************************************************/
class Solution {
    public int findShortestSubArray(int[] nums) {
        int[] counts = new int[50000];
        for (int num : nums)
            counts[num]++;
        int degree = -1;
        Set<Integer> degreeNums = new HashSet<> ();
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] > degree) {
                degree = counts[i];
                degreeNums.clear ();
                degreeNums.add (i);
            } else if (counts[i] == degree) {
                degreeNums.add (i);
            }
        }
        assert !degreeNums.isEmpty ();
        int resLen = nums.length + 1;
        for (int degreeNum : degreeNums) {
            int lo = 0, hi = nums.length - 1;
            while (lo < nums.length && nums[lo] != degreeNum)
                lo++;
            while (hi >= 0 && nums[hi] != degreeNum)
                hi--;
            assert hi >= lo; 
            int curLen = hi - lo + 1;
            resLen = Math.min (resLen, curLen);
        }
        assert resLen <= nums.length;
        return resLen;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        DegreeOfAnArray.Solution tester = new DegreeOfAnArray.Solution();
        int[][] inputs = {
            {1, 2, 2, 3, 1}, {2},
            {1,2,2,3,1,4,2}, {6},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[] nums = inputs[2 * i];
            int ans = inputs[2 * i + 1][0];
            System.out.println (Printer.separator ());
            int output = tester.findShortestSubArray (nums);
            System.out.printf ("%s -> %s, expected: %d\n",
                Printer.array (nums), Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

题目大概看了一下, 笨办法很简单, 先走一遍来一个counts, 然后找到counts最大的(用bucket sort可以控制这一步的复杂度), 然后找leftmost和rightmost occurrence就行了. 但是感觉好像可以有更好的办法, 毕竟bucket sort虽然可以控制时间复杂度, 但是是以牺牲空间复杂度为前提的;

想了一下, 这里要找的只是maximum count的, 所以其实没有必要bucket sort, 最后全部做完之后过一遍找一个max就行了; 不过因为这题限制了domain, 所以还是直接用array count而不是Map算了;

这题有一个小细节, 就是怎么处理tie的情况, 这个体现在第一个test里面, 如果你最后选择的是1(和2一样, count都是2), 那么你最后的答案就不对; 解决方案并不难, 加一个循环就行了, 但是关键是自己面试的时候要想到;

要不说手生了呢, 这么简单的一个题目最后也是花了不少时间, 按理是可以秒杀的: 除了tie这个问题, 这个题目几乎没有任何暗坑. 最后的速度是82ms (21%), 也不算满意;

这个题目总体思路上还是比较清晰的, 但是最后代码能写成什么样, 好像变数其实还是挺大的. 这个是editorial:

class Solution {  
    public int findShortestSubArray(int[] nums) {  
        Map<Integer, Integer> left = new HashMap(),  
            right = new HashMap(), count = new HashMap();  

        for (int i = 0; i < nums.length; i++) {  
            int x = nums[i];  
            if (left.get(x) == null) left.put(x, i);  
            right.put(x, i);  
            count.put(x, count.getOrDefault(x, 0) + 1);  
        }  

        int ans = nums.length;  
        int degree = Collections.max(count.values());  
        for (int x: count.keySet()) {  
            if (count.get(x) == degree) {  
                ans = Math.min(ans, right.get(x) - left.get(x) + 1);  
            }  
        }  
        return ans;  
    }  
}

这个是写的非常漂亮的一个代码, 虽然总体思路上跟我的类似, 但是很多地方都有优化; 需要注意的两个地方:

• 他整个过程只要一个pass. 注意看他记录leftmost和rightmost的更新方式, 怎么放在一起一遍头就可以写掉;
• Collections.max(count.values()), 这里是两个我不太熟悉的API;

整个代码可以说是非常的简练;

这个是discussion里面一个类似的做法, 不过不借助于Collections.max:

@compton_scatter said in Java O(n) Time O(n) Space:

1) Get degree of array, frequency of all integers in array, and the indices of the first and last occurrence of each integer in the array
2) Return the minimum occurrence range of each integer which appears degree number of times in the array,

public int findShortestSubArray(int[] nums) {  
    int degree = 0, n = nums.length, minSize = n;  
    Map<Integer, Integer> map = new HashMap<>();  
    Map<Integer, Integer[]> map2 = new HashMap<>();  

    for (int i=0;i<n;i++) {  
        map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);  
        degree = Math.max(degree, map.get(nums[i]));  

        if (map2.get(nums[i]) == null) map2.put(nums[i], new Integer[2]);  
        Integer[] numRange = map2.get(nums[i]);  
        if (numRange[0] == null) numRange[0] = i;  
        numRange[1] = i;  
    }  

    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {  
        if (entry.getValue() != degree) continue;  
        Integer[] range = map2.get(entry.getKey());  
        minSize = Math.min(minSize, range[1] - range[0] + 1);    
    }  
    return minSize;  
}

他求max的做法就是直接整合到1pass里面去做; 注意他们这些人的做法都有一个好处, 就是不需要像我那样, 为了解决tie的问题, 还要专门加一个循环结构进去;

底下回复有很多这种写法:

@williampmb said in Java O(n) Time O(n) Space:

I think you don't need to go over the map after going the entire array.
You could be checking who is the smallest subarray in the first loop.

 public int findShortestSubArray(int[] nums) {  
        Map<Integer, int[]> db = new Hashtable<>();  
        int size = nums.length;  
        int degree = 0;  
        int smallestSubarray = 50001;  
        for (int i = 0; i < size; i++) {  
            int[] data;  
            if (db.containsKey(nums[i])) {  
                data = db.get(nums[i]);  
            } else {  
                data = new int[3];  
                data[1] = i;  
            }  
            data[2] = i;  
            data[0] += 1;  

            db.put(nums[i], data);  
            if (data[0] > degree) {  
                degree = data[0];  
                smallestSubarray = data[2] - data[1] + 1;  
            }else if (degree == data[0]) {  
                smallestSubarray = data[2] - data[1] + 1 < smallestSubarray ? data[2] - data[1] + 1 : smallestSubarray;  
            }  
        }  

        return smallestSubarray;  
    }

这些人为了省几个HashMap也是无所不用其极, 但是注意, 这种看起来是优化的东西, 其实是自己给自己找事情做, 因为NLP的时候Jason就说过, 这种Collection of Collectios结构其实对速度非常的不利, 完全比不过collection of small hashmaps, 所以真的不用模仿这种东西;

不过很奇怪的是, 这种写法最后OJ给出的速度反而非常好, 80%左右的速度, 不知道是为什么;

submission最优解: 13(99):

class Solution {  
    public int findShortestSubArray(int[] nums) {  
        if (nums == null || nums.length == 0)  
            return 0;  
        int maxNum = 0;  
        for (int n : nums){  
            maxNum = Math.max(n, maxNum);  
        }  

        int[] start = new int[maxNum + 1];  
        int[] end = new int[maxNum + 1];  
        int[] que = new int[maxNum + 1];  

        for (int i = 0; i < nums.length; i++){  
            if (que[nums[i]] == 0)  
                start[nums[i]] = i;  
            end[nums[i]] = i;  
            que[nums[i]]++;  
        }  

        int max = 0;  
        for (int n : que)  
            max = Math.max(max, n);  

        List<Integer> maxNums = new ArrayList<>();  
        for (int i = 0; i < que.length; i++){  
            if (que[i] == max)  
                maxNums.add(i);  
        }  

        int res = nums.length;  
        for (int n : maxNums){  
            int r = end[n] - start[n] + 1;  
            res = Math.min(r, res);  
        }  

        return res;  
    }  
}

基本也没啥区别, 就是用array来避免java本身的collection的overhead而已; 实际上整个代码过程当中做了很多个pass;

注意他这里先走一遍来获得 maxNum的做法, 这个是在bucket sort问题当中很常见的技巧了, 应该不陌生;

Problem Description

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

Note:

• nums.length will be between 1 and 50,000.
• nums[i] will be an integer between 0 and 49,999.

Difficulty:Easy
Total Accepted:12.3K
Total Submissions:26.2K
Contributor:fishercoder
Companies
ge digital
Related Topics
array
Similar Questions
Maximum Subarray

Hide Hint 1

Say 5 is the only element that occurs the most number of times - for example, nums = [1, 5, 2, 3, 5, 4, 5, 6]. What is the answer?