优化子数组公共最小元素求解算法：降低时空复杂度

给定长度为n的整数数组，对k从1到n的每个取值，找出所有长度为k的子数组的公共元素中的最小值；若无公共元素，则返回-1，将结果存入列表。

示例 #

输入数组：[4,3,3,4,2]
结果：[-1,-1,3,3,2]
解释：

• k=1时，子数组为[4]、[3]、[3]、[4]、[2]，无公共元素，返回-1
• k=2时，子数组为[4,3]、[3,3]、[3,4]、[4,2]，无公共元素，返回-1
• k=3时，子数组为[4,3,3]、[3,3,4]、[3,4,2]，公共元素为3
• k=4时，子数组为[4,3,3,4]、[3,3,4,2]，公共元素为3、4，最小值为3
• k=5时，子数组为[4,3,3,4,2]，公共最小元素为2

约束条件 #

• 数组长度n的范围为2到10^5
• 数组元素取值范围为1到n

初始朴素解法时间复杂度为O(n³)，且使用Map存储所有子数组导致空间复杂度较高；改进后的解法时间复杂度为O(n²)，仍需进一步优化时间与空间复杂度。

初始朴素代码 #

public static List<Integer> solve(int[] ar) {
    // 获取所有子数组，键为子数组长度1到n，值为对应长度的子数组列表
    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);
        // 获取公共元素最小值并存入结果
        result.add(solve(list));
    }
    return result;
}
// 给定某一长度k的子数组列表，找出公共元素中的最小值
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; // 无公共元素则返回-1
}

// 检查数字是否存在于给定数组中
public static boolean contains(List<Integer> arr, int num) {
    for (int value : arr) {
        if (value == num) {
            return true;
        }
    }
    return false;
}
// 找出所有长度1到n的子数组并存入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;
}

改进后代码（已修正语法错误） #

public static List<Integer> solve(int[] ar) {
    int n = ar.length; // 原代码误用map.size()，修正为数组实际长度
    List<Integer> result = new ArrayList<>();
    for(int i=0; i<n; i++) {
        result.add(minCommonElementInSubarrays(ar, i+1));
    }
    return result;
}

static int minCommonElementInSubarrays(int arr[], int K) { // 原代码返回值类型错误，修正为int
    int N = arr.length;
    int c; 
   
    // 若N为奇数，更新c为K >= (N + 1)/2
    if ((N + 1) % 2 == 0) 
    { 
        c = (N + 1) / 2; 
    } 
   
    // 若N为偶数，更新c为K >= (N + 1)/2 + 1
    else
    { 
        c = (N + 1) / 2 + 1; 
    } 
   
    // 若K < c，返回-1
    if (K < c)
    { 
        return -1;
    } 
   
    // 否则
    else
    { 
        // 初始化结果变量
        int minVal = Integer.MAX_VALUE; 
        // 修正循环范围，遍历所有长度为K的子数组的起始位置元素
        for(int i = 0; i <= N - K; i++)
        { 
            minVal = Math.min(arr[i], minVal); 
        } 
        // 返回最小值
        return minVal;
    } 
}

寻求时间复杂度低于O(n²)、空间复杂度更优的解决方案。

内容的提问来源于stack exchange，提问作者Learner