如何求N个组合R中的第k项

推荐答案

时间复杂度为O(Kn)，空间复杂度为O(N)

public static void main(String[] args) {
    //n = 4, r = 2, k = 3
    int[] ret1 = getKthPermutation(4, 2, 3);
    //ret1 is [1,0,0,1]

    //n = 3, r = 2, k = 1
    int[] ret2 = getKthPermutation(3, 2, 1);
    //ret2 is [1,0,1]
}

static int[] getKthPermutation(int n, int r, int k) {
    int[] array = new int[n];
    setLastN(array, r, 1);

    int lastIndex = n - 1;
    for(int count = 0; count < k; count++) {

        int indexOfLastOne = findIndexOfLast(array, lastIndex, 1);
        int indexOfLastZero = findIndexOfLast(array, indexOfLastOne, 0);
        array[indexOfLastOne] = 0;
        array[indexOfLastZero] = 1;

        //shortcut: swap the part after indexOfLastZero to keep them sorted
        int h = indexOfLastZero + 1;
        int e = lastIndex;
        while(h < e) {
            int temp = array[h];
            array[h] = array[e];
            array[e] = temp;
            h++;
            e--;
        }

    }

    return array;
}

//starting from `from`, and traveling the array forward, find the first `value` and return its index.
static int findIndexOfLast(int[] array, int from, int value) {
    for(int i = from; i > -1; i--)
        if(array[i] == value) return i;
    return -1;
}

//set the last n elements of an array to `value`
static void setLastN(int[] array, int n, int value){
    for(int i = 0, l = array.length - 1; i < n; i++)
        array[l - i] = value;
}

这是非常典型的"寻找第k个变形"算法的改编。

我将尝试解释一般概念(您的是一个特例，因为只有两种类型的元素：0和1)。 假设我有[2,1,6,4,7,5]。下一个最小的排列比现在的排列大的是什么？为什么我要关注比当前排列更大的下一个最小排列呢？因为如果您从最小的排列[1,2,4,5,6,7]开始，并将该操作重复k次(找到比当前大的最小的排列)，您将找到第k+1个最小的排列。

现在，由于我要查找的值需要大于当前值，因此需要递增当前值。为了使增量尽可能小，我将尝试修改5(最后一个)。现在，我不能只将5更改为随机值，我只能将其与其前面的某个数字交换。

在我们的例子中，有两点不同： 1.我们需要交换最后一个1，因为您不能通过将a 0与它之前的任何数字交换来使排列更大。 2.我们始终可以使用代码中所示的快捷方式对后缀进行排序。我将把它留给您：)

这篇关于如何求N个组合R中的第k项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！