查找陣列中具有最大度數的最小子陣列的長度

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）