查找给定数组的唯一值或组合

Question

我有一个大小为 n 的数字数组，选择数组中所有可能的不同递增子序列，为每个子序列找到按位或值并按递增顺序返回它们作为结果。

示例：

arr= [4,2,4,1], n = 4

结果

[1,2,4,6]

说明：

All possible distinct increasing subsequences are:
[4]
[2]
[2, 4]
[1]

Bit wise or values are:
[4]
[2]
[2 | 4] = [6]
[1]

So values are [2,4,6, 1]
sorted result is [1,2,4,6]

另一个例子：

arr = [3,2,4,6], n = 4

结果

[2,3,4,6,7]

说明：

All increasing subsequences and corresponding bitwise or values are:
[3] : 3
[3, 4] : 7
[3, 4, 6] : 7
[3, 6] : 7
[2] : 2
[2, 4] : 6
[2, 4, 6] : 6
[2, 6] : 6
[4] : 4
[4, 6] : 6
[6] : 6

So distinct values are [3,7,2,6,4]
sorted result is [2,3,4,6,7]

限制：

1 <= n <= 10^4
1 <= arr[i] <= 1024

我已经使用暴力方法解决了它，这是我的代码：

import java.util.*;

public class Main {

    public static void main(String[] args) {
        int[] arr = {3,2,4,6};

        List<List<Integer>> subsequences = findIncreasingSubsequences(arr);

        Set<Integer> set = new TreeSet<>();
        for (List<Integer> subsequence : subsequences) {
            int or = subsequence.get(0);
            for(int i=1; i<subsequence.size(); i++) {
                or |= subsequence.get(i);
            }
            //System.out.println(subsequence + " : "+ or);
            set.add(or);
        }
        System.out.println("Result : " + set);
    }

    public static List<List<Integer>> findIncreasingSubsequences(int[] arr) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();

        findSubsequences(arr, result, current, 0);

        return result;
    }

    private static void findSubsequences(int[] arr, List<List<Integer>> result, List<Integer> current, int start) {
        if (!current.isEmpty()) {
            result.add(new ArrayList<>(current)); // Add current subsequence to result
        }

        for (int i = start; i < arr.length; i++) {
            if (current.isEmpty() || arr[i] > current.get(current.size() - 1)) {
                current.add(arr[i]);
                findSubsequences(arr, result, current, i + 1);
                current.remove(current.size() - 1);
            }
        }
    }
}

如何以较少的时间复杂度解决这个问题。

Answer 1

我认为如果不尝试所有可能的组合，你就无法摆脱困境。但如果这些分支不能产生新的结果，你当然可以修剪掉很多分支。

这是我的代码。我有与你类似的方法，但我并没有真正计算所有组合，而是只是传递了当前组合的或值。如果采用下一个元素不会得到您之前见过的新或值，则修剪完成。

import java.util.*;
 
class Solution {
    void solve(List<Integer> nums, int index, int lastIndex, int taken, int curr, Set<Integer> values) {
        if (taken > 0) {
            values.add(curr);
        }
        if (index >= nums.size()) {
            return;
        }
 
        // Take it.
        if (lastIndex == -1 || nums.get(index) > nums.get(lastIndex)) {
            int newOrValue = curr | nums.get(index);
            if (!values.contains(newOrValue)) {
                solve(nums, index + 1, index, taken + 1, newOrValue, values);
            }
        }
        // Leave it
        solve(nums, index + 1, lastIndex, taken, curr, values);
    }
 
    public List<Integer> getIncreasingSubsequenceOrValues(List<Integer> nums) {
        Set<Integer> values = new HashSet<>();
        solve(nums, 0 /* index */, -1 /* lastIndex */, 0 /* taken */, 0 /* curr */, values);
        return new ArrayList<>(values);
    }
}
 
public class Main {
    static void print(List<Integer> v) {
        for (int el : v) {
            System.out.print(el + " ");
        }
        System.out.println();
    }
 
    static void test(List<Integer> nums) {
        System.out.print("Testing for array: ");
        print(nums);
 
        Solution solution = new Solution();
        List<Integer> result = solution.getIncreasingSubsequenceOrValues(nums);
 
        print(result);
    }
 
    public static void main(String[] args) {
        test(Arrays.asList(4, 2, 4, 1));
        test(Arrays.asList(3, 2, 4, 6));
    }
}

可运行于：https://ideone.com/NmfuVV