本文介紹了如何求N個組合R中的第k項的處理方法，對大家解決問題具有一定的參考價值，需要的朋友們下面隨著小編來一起學習吧！
問題描述
如何在NCR中獲取kth組合。而不需要迭代所有可能的結果。例如，假設我對3個位置和2個相同的項目有3C2個。我知道是[011]、[101]和[110]。例如，如何使用方法獲取[101]的第二項(k=1)？
約束(R < Nk >= 0和k < PwhereP = NCR)。
NB：
[101]是第二個術語(以升序/詞典順序)，因為011=3，101=5，110=6
以十進制表示。所以基本上目標是得到ncr中的k是多少，
因為NCR的每個kth輸出都可以用數字表示。
推薦答案
時間復雜度為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更改為隨機值，我只能將其與其前面的某個數字交換。
如果我將5與前面的一個更大的數字交換，比如7，那么我將得到[2,1,6,4,5,7]，它比當前的小。很明顯，我需要把5換成更小的數字，但換的是哪一個呢？如果我用5換2，我得到[5,1,6,4,7,2]，這個增量太大了。我需要將5換成”較低的數字”，以保持盡可能小的增量。這將使我們找到小于5的第一個(最低)數字(從右到左)。在這種情況下，我需要將5替換為4并得到[2,1,6,5,7,4]。這樣一來，我就可以讓”掉期”的影響變得很小。現在決定了前綴[2,1,6,5。沒有更小的前綴了。我們需要處理后綴7,4]。顯然，如果我們對后綴進行排序并使其4,7]，那么我們就完成了。
在我們的例子中，有兩點不同：
1.我們需要交換最后一個1，因為您不能通過將a 0與它之前的任何數字交換來使排列更大。
2.我們始終可以使用代碼中所示的快捷方式對后綴進行排序。我將把它留給您：)
這篇關于如何求N個組合R中的第k項的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，
