在最佳时间复杂度下求未排序整数数组中两个相同数之间的最大差值[Java]

Question

static int solution(int[] A) {
    int N = A.length;
    int result = 0;
    Map<Integer, List<Integer>> map = new TreeMap<>();
    for (int i = 0; i < N; i++) {
        List<Integer> list = map.getOrDefault(A[i], new ArrayList<>());
        list.add(i);
        map.put(A[i], list);

    }
    for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
        List<Integer> list = map.get(entry.getKey());
        Collections.sort(list);
        result = Math.max(result, (list.get(list.size() - 1) - list.get(0)));
    }
    return result;
}

通过上述解决方案，我们可以解决这个问题，但它不是O（N）时间复杂度。因此，我正在寻找一个用Java解决这个问题的优化方案。

Answer 1

//收藏。排序（列表）//删除这一行会使O（NlogK）到O（N）的时间复杂度增加

  static int solution(int[] A) {
    int N = A.length;
    int result = 0;
    Map<Integer, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < N; i++) {
        List<Integer> list = map.getOrDefault(A[i], new ArrayList<>());
        list.add(i);
        map.put(A[i], list);

    }
    for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
        List<Integer> list = map.get(entry.getKey());
        result = Math.max(result, (list.get(list.size() - 1) - list.get(0)));
    }
    return result;
}