查找阵列中具有最大度数的最小子阵列的长度

Question

我试图解决hackerrank中的一个问题，该问题是查找数组中具有最大度数的最小子阵列的长度。数组的最大度数是具有最大频率的元素的数量。例如，考虑例子{2,2,1,2,3,1,1}最小子数组长度为4，因为2具有最大度数，并且具有度数3的最小子数组是{2，2， 1，2}

下面是我的问题

public class FindingMinSubArrayWithDegree { 
    public static void main(String[] args) { 
     Scanner sc = new Scanner(System.in); 
     int n = sc.nextInt(); 
     int[] arr = new int[n]; 
     for (int i = 0; i < n; i++) { 
      arr[i] = sc.nextInt(); 
     } 
     System.out.println(degreeOfArray(arr)); 
     sc.close(); 
    } 

    static int degreeOfArray(int[] arr) { 
     HashMap<Integer, Integer> numbersByDegree = new HashMap<Integer, Integer>(); 
     for (int i = 0; i < arr.length; i++) { 
      int degree = numbersByDegree.getOrDefault(arr[i], 0); 
      numbersByDegree.put(arr[i], degree + 1); 
     } 
     List<Map.Entry<Integer, Integer>> sortedEntries = sortByValue(numbersByDegree); 
     int maxDegree = sortedEntries.get(0).getValue(); 

     int[] degreeArr = new int[arr.length] ; 
     int minSubArrayLength = arr.length; 
     for (Map.Entry<Integer, Integer> entry : sortedEntries) { 
      if (entry.getValue() < maxDegree) { 
       break; 
      } 
      boolean startIndexFound = false, endIndexFound = false; 
      int startIndex = 0, endIndex = 0; 
      for (int i = 0; i < arr.length; i++) { 
       if (entry.getKey() == arr[i]) { 
        if (i - 1 >= 0) 
         degreeArr[i] = degreeArr[i - 1] + 1; 
        else 
         degreeArr[i] = 1; 
       } else { 
        if (i - 1 >= 0) 
         degreeArr[i] = degreeArr[i - 1]; 
       } 
       if (!startIndexFound && degreeArr[i] == 1) { 
        startIndex = i; 
        startIndexFound = true; 
       } 
       if (!endIndexFound && degreeArr[i] == entry.getValue()) { 
        endIndex = i; 
        endIndexFound = true; 
       } 
       if (startIndexFound && endIndexFound) 
        break; 
      } 
      startIndexFound = false; endIndexFound = false; 
      if ((endIndex - startIndex) < minSubArrayLength) { 
       minSubArrayLength = endIndex - startIndex; 
      } 
      for (int i = 0; i < degreeArr.length; i++) 
       degreeArr[i] = 0; 
     } 
     return minSubArrayLength + 1; 
    } 

    private static <K, V extends Comparable<? super V>> List<Map.Entry<K, V>> 
    sortByValue(Map<K, V> map) { 
     List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>(map.entrySet()); 
     Collections.sort(list, new Comparator<Map.Entry<K, V>>() { 
      public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) { 
       return (o2.getValue()).compareTo(o1.getValue()); 
      } 
     }); 
     return list; 
    } 
} 

这种方法具有运行的O时的最坏情况的解决方案（N^2），用于像{1，1，2，2，3的输入，3,4,4}。这个问题有更好的算法吗？

PS - 我试着问在代码审查这个问题，但没有得到，这就是为什么搬到这里

Answer 1

要找到一个数组的程度有任何回应，我们只需要保持各个不同的频率轨道元素，那些频率最高的元素就是度数。

因此，要找到最大程度的子阵，我们只需要关心的是包含具有最大计数元素的子阵，这意味着所有[start , end]子阵列的起点和终点的发生那个元素。

因此，我们需要做的是跟踪每个元素的频率，开始和结束位置。

伪代码：

int max = 0; 
Map<Integer, Integer> map = new HashMap<>(); 
Map<Integer, Integer> startIndex = new HashMap<>(); 
Map<Integer, Integer> endIndex = new HashMap<>(); 
for(int i = 0; i < data.length; i++){ 
    int value = data[i]; 
    if(map.containsKey(value)){ 
     map.put(value, map.get(value) + 1); 
    }else{ 
     startIndex.put(value, i); 
     map.put(value, 1); 
    } 
    endIndex.put(value, i); 
    max = Integer.max(max, map.get(value));//Calculate the degree of the array 
} 
int result = data.length; 
for(int i : map.keySet()){ 
    if(map.get(i) == max){ 
     int len = endIndex.get(i) - startIndex.get(i) + 1; 
     result = Integer.min(result, len); 
    } 
} 
return result; 

时间复杂度是O（n）

Answer 2

鉴于非负整数NUMS的非空数组，该数组的程度被定义为最大频率它的任何一个元素。

我们将创建3个HashMap。

• 记住每个元素的频率 - HashMap的计数的每个元素第一次发生的
• 指数 - HashMap中留下的每个元素的最后一次出现的
• 指数 - HashMap的权利。

然后我们将遍历Count（HashMap）并比较最大频率，如果等于最大频率那么我们将找到一个（连续）子数组的长度。

CODE： -

class Solution { 
public int findShortestSubArray(int[] nums) { 
    int n = nums.length; 
    int degree = 0; 
    HashMap<Integer,Integer> count = new HashMap<Integer,Integer>(); 
    HashMap<Integer,Integer> left = new HashMap<Integer,Integer>(); 
    HashMap<Integer,Integer> right = new HashMap<Integer,Integer>(); 
    for(int i = 0;i<n;i++){ 
     count.put(nums[i],count.getOrDefault(nums[i],0)+1); 
     if(!left.containsKey(nums[i]))left.put(nums[i],i); 
     right.put(nums[i],i); 
     degree = Math.max(degree,count.get(nums[i])); 
    } 
    int len ; 
    int result = n; 
    for(int c : count.keySet()){ 
     if(count.get(c)==degree){ 
      len = right.get(c)-left.get(c)+1; 
      if(len < result) 
       result = len; 
     } 

    } 
    return result; 

} 

}

时间Complexcity O（N） 空间Complexcity O（N）