降低处理子数组的时间复杂度

Question

对于给定的大小为 n 的整数数组，找到大小为 k 且范围从 1 到 n 的所有可能的子数组。

现在找到大小为 k 的所有子数组中最小的公共项，如果没有找到公共项，则使用 -1 并将其添加到结果列表中。

例如：

Input array : [4,3,3,4,2]

结果：

[-1,-1,3,3,2]

说明：

k = 1, [4],[3],[3],[4],[2], there is no common item so -1
k = 2, [4,3],[3,3],[3,4],[4,2], there is no common item so -1
k = 3, [4,3,3], [3,3,4], [3,4,2], common item is 3
k = 4, [4,3,3,4],[3,3,4,2], common items are 3 and 4, the minimum is 3
k = 5, [4,3,3,4,2], minimum common item is 2

限制：

size (n) of the array range is 2 to 10^5
Each array element range is 1 to n

这是我幼稚的方法代码以及注释：

public static List<Integer> solve(int[] ar) {
    // Get all subarrays in a map, with key as sub-arrays size from 1 to n and value as the corresponding sub-arrays 
    Map<Integer, List<List<Integer>>> map = subArrays(ar);
    int n = map.size();
    List<Integer> result = new ArrayList<>();
    for(int i=0; i<n; i++) {
        List<List<Integer>> list = map.get(i+1);
        // Get the common minimum item and store in result.
        result.add(solve(list));
    }
    return result;
}
// Logic to check for a given subarray of size k, get the minimum common item
public static int solve(List<List<Integer>> list) {
    int n = list.get(0).size();
    int min = Integer.MAX_VALUE;
    boolean found = false;
    for (int i = 0; i < n; i++) {
        int num = list.get(0).get(i);
        boolean isCommon = true;
        
        for(int j=1; j<list.size(); j++) {
            List<Integer> arr = list.get(j);
            if (!contains(arr, num)) {
                isCommon = false;
                break;
            }
        }

        if (isCommon) {
            min = Math.min(min, num);
            found = true;
        }
    }

    return found ? min : -1; // Return -1 if there is no common element.
}

// Logic to check if the number is present in given arr
public static boolean contains(List<Integer> arr, int num) {
    for (int value : arr) {
        if (value == num) {
            return true;
        }
    }
    return false;
}
// Logic to find all possible sub arrays of size 1 to n and stored in map
public static Map<Integer, List<List<Integer>>> subArrays(int[] arr) {
    int n = arr.length;
    Map<Integer, List<List<Integer>>> map = new HashMap<>();
    for(int i=0; i<n; i++) {
        map.put(i+1, new ArrayList<>());
    }
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int size = j - i+1;
            List<Integer> e = new ArrayList<>();
            for (int k = i; k <= j; k++) {
                e.add(arr[k]);
            }
            map.get(size).add(e);
        }
    }
    return map;
}

}

这里我使用嵌套循环，因此时间复杂度为 O(n^3)，还使用映射来存储所有可能的子数组，这增加了空间复杂度。

如何在更少的时间和空间内解决这个问题。

更新：

我进一步尝试使用下面的代码来降低时间复杂度：

public static List<Integer> solve(int[] ar) {
    int n = map.size();
    List<Integer> result = new ArrayList<>();
    for(int i=0; i<n; i++) {
        result.add(minCommonElementInSubarrays(ar, i+1));
    }
    return result;
}

static void minCommonElementInSubarrays(int arr[], int K) { 
    int N = arr.length;
    int c; 
   
    // If N is odd then update 
    // C as K >= (N + 1)/2 
    if ((N + 1) % 2 == 0) 
    { 
        c = (N + 1) / 2; 
    } 
   
    // If N is even then update 
    // C as K >= (N + 1)/2 + 1 
    else
    { 
        c = (N + 1) / 2 + 1; 
    } 
   
    // If K < C, return "=1" 
    if (K < c)
    { 
        return -1;
    } 
   
    // Otherwise 
    else
    { 
         
        // Initialize result variable 
        int ar = Integer.MAX_VALUE; 
   
        // Find minimum element 
        for(int i = N - K; i < K; i++)
        { 
            ar = Math.min(arr[i], ar); 
        } 
   
        // return the minimum value 
        return ar;
    } 
}

但是这段代码的运行时间复杂度仍然是 O(n^2)，我想进一步减少它。

Answer 1

在线性时间和空间中，将数组中的每个元素映射到其实例之间的最大间隙以及数组的开头和结尾。为此，您只需跟踪到目前为止每个索引看到的最大间隙以及每个 elt 看到的最后一个索引。

例如对于 [4,3,3,4,2]

elt => max gap:
  2 => 4
  3 => 2
  4 => 2

然后，对于给定的 k 值，有间隙的最小值 <= k-1 is the answer.

k=1: There's no gap of 0, so -1
k=2: There's no gap of 1, so -1
k=3: 3 & 4 both have a max gap <= 2, so min(3,4) = 3
k=4: 3 & 4 both have a max gap <= 3, so min(3,4) = 3
k=5: 2,3,4 all have a max gap <= 4, so min(2,3,4) = 2.

这也可以在线性时间和空间中完成；只需创建地图gap_to_min_elt并检查所有可能的间隙。