在数组中查找具有最大度数的最小子数组的长度

Question

我尝试在hackerrank中解决一个问题,即找到数组中最大度数的最小子数组的长度.数组的最大度数是具有最大频率的元素的数量.例如,考虑示例{2,2,1,2,3,1,1} min子阵列长度为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;
    }
}

对于诸如{1,1,2,2,3,3,4,4}的输入,该方法具有O(N ^ 2)的最差情况运行时间.这个问题有更好的算法吗？

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)