algorithm - 从 N 个整数数组中选择有序三元组的不同方法

Question

给定一个包含 n 个整数的数组 A，我想找到选择有序三元组的方法。例如。

A = [1, 2, 1, 1]
different ways are  (1, 2, 1), (1, 1, 1) and (2, 1, 1)
so the answer will be 3.

for A = [2, 2, 1, 2, 2]
different ways are (1, 2, 2), (2, 1, 2), (2, 2, 1) and (2, 2, 2)
so the answer will be 4 in this case

如果所有数字都是唯一的，那么我想出了一个循环

f(n) = f(n-1) + ((n-1) * (n-2))/2
where f(3) = 1 and f(2) = f(1) = 0

当数字重复时，我遇到了麻烦。这需要在 O(n) 时间和 O(n) 空间内解决。

Answer 1

对于大小为 idx 的数组，唯一有序集合的数量的动态规划关系是:

DP[集合大小][idx] = DP[集合大小][idx-1] + DP[集合大小 - 1][idx-1] - DP[集合大小 - 1][ last_idx[ A[idx] - 1]

因此，要从 idx 元素数组中计算大小为 LEN 的有序且唯一集合的数量:

• 获取可以从 idx-1 个元素的数组中创建的大小为 LEN 的有序唯一集的数量
• 添加可通过将元素 idx 添加到大小为 LEN-1 的有序唯一集合的末尾而形成的有序唯一集合的数量
• 不要重复计算。减去可通过将先前出现的元素 idx 添加到大小为 LEN-1 的有序唯一集的末尾而形成的有序唯一集的数量。

这是有效的，因为我们在遍历数组时总是计算唯一集合。计算唯一集合是基于以前的唯一集合的元素计数。

所以，从 1 号的组开始，然后是 2 号，然后是 3 号，等等。

对于固定大小 LEN 的唯一有序集合，我的函数占用 O(LEN * N) 内存和 O(LEN * N) 时间。您应该能够重用 DP 数组以将内存减少为独立于 LEN 的常量，O(constant * N)。

这是函数。

    static int answer(int[] A) {
    // This example is for 0 <= A[i] <= 9.  For an array of arbitrary integers, use a proper
    //   HashMap instead of an array as a HashMap. Alternatively, one could compress the input array
    //   down to distinct, consecutive numbers. Either way max memory of the last_idx array is O(n).
    //   This is left as an exercise to the reader.
    final int MAX_INT_DIGIT = 10;
    final int SUBSEQUENCE_LENGTH = 3;
    int n = A.length;

    int[][] dp = new int[SUBSEQUENCE_LENGTH][n];
    int[] last_idx = new int[MAX_INT_DIGIT];
    Arrays.fill(last_idx, -1);

    // Init dp[0] which gives the number of distinct sets of length 1 ending at index i
    dp[0][0] = 1;
    last_idx[A[0]] = 0;

    for (int i = 1; i < n; i++) {
        if (last_idx[A[i]] == -1) {
            dp[0][i] = dp[0][i - 1] + 1;
        } else {
            dp[0][i] = dp[0][i - 1];
        }
        last_idx[A[i]] = i;
    }

    for (int ss_len = 1; ss_len < SUBSEQUENCE_LENGTH; ss_len++) {
        Arrays.fill(last_idx, -1);
        last_idx[A[0]] = 0;
        for (int i = 1; i < n; i++) {
            if (last_idx[A[i]] <= 0) {
                dp[ss_len][i] = dp[ss_len][i - 1] + dp[ss_len-1][i - 1];
            } else {
                dp[ss_len][i] = dp[ss_len][i - 1] + dp[ss_len-1][i - 1] - dp[ss_len-1][last_idx[A[i]] - 1];
            }
            last_idx[A[i]] = (i);
        }
    }

    return dp[SUBSEQUENCE_LENGTH-1][n - 1];
}

对于 [3 1 1 3 8 0 5 8 9 0]，我得到的答案是 62。