資訊專欄INFORMATION COLUMN
摘要：找規(guī)律復(fù)雜度時(shí)間空間思路由于我們只要得到第個(gè)全排列，而不是所有全排列，我們不一定要將所有可能都搜索一遍。根據(jù)全排列順序的性質(zhì)，我們可以總結(jié)出一個(gè)規(guī)律假設(shè)全排列有個(gè)數(shù)組成，則第個(gè)全排列的第一位是。然后將得到，這個(gè)就是下一輪的。
Permutation Sequence
找規(guī)律 復(fù)雜度The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):
"123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
時(shí)間 O(N) 空間 O(1)
思路由于我們只要得到第K個(gè)全排列，而不是所有全排列，我們不一定要將所有可能都搜索一遍。根據(jù)全排列順序的性質(zhì)，我們可以總結(jié)出一個(gè)規(guī)律：假設(shè)全排列有n個(gè)數(shù)組成，則第k個(gè)全排列的第一位是k/(n-1)!。為了更形象一點(diǎn)，舉例如下：
123 132 213 231 312 321
在這種情況下，第一個(gè)數(shù)字每2!=2個(gè)情況就改變一次，假設(shè)求第6個(gè)排列，我們先將其減1，方便整除運(yùn)算，然后5/2=2。對(duì)于第一位，我們有三種可選數(shù)字1、2、3，所以5/2=2意味著我們選擇第3個(gè)數(shù)字，也就是3（如果商是s，則選第s+1個(gè)數(shù)字）。然后將5%2得到1，這個(gè)1就是下一輪的k。
注意這里有一個(gè)技巧，就是用一個(gè)列表將1到n存起來，每選用一個(gè)數(shù)就是移出那個(gè)數(shù)，就能保證不選重復(fù)數(shù)字的同時(shí)，其順序也是一樣的。
代碼public class Solution {
public String getPermutation(int n, int k) {
int mod = 1;
List candidates = new ArrayList();
// 先得到n!和候選數(shù)字列表
for(int i = 1; i <= n; i++){
mod = mod * i;
candidates.add(i);
}
// 將k先減1方便整除
k--;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < n ; i++){
mod = mod / (n - i);
// 得到當(dāng)前應(yīng)選數(shù)字的序數(shù)
int first = k / mod;
// 得到用于計(jì)算下一位的k
k = k % mod;
sb.append(candidates.get(first));
// 在列表中移出該數(shù)字
candidates.remove(first);
}
return sb.toString();
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/64559.html
摘要：題目要求假設(shè)按照題中給的排列組合的順序，假設(shè)有個(gè)數(shù)字，返回第個(gè)排列組合的結(jié)果。最后在個(gè)位上，選擇中的第一個(gè)。這時(shí)知道以第位為開頭的結(jié)果值有此時(shí)第個(gè)結(jié)果集在該位上的選擇為。依次往后類推，直至到最后一位。 題目要求 The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling...
摘要：我們所找到的這個(gè)元素就是排序需要改變的第一個(gè)元素。然后我們選取一個(gè)剛好大于此元素的數(shù)，與當(dāng)前元素進(jìn)行替換。并對(duì)后面的所有元素重新按照升序排列就可以得到最終的答案。 題目詳情 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of...
摘要：因?yàn)樵黾痈呶粫?huì)帶來更大的增益。所以對(duì)于一個(gè)長(zhǎng)為的序列，我們?cè)黾拥谖坏那疤崾牵拔灰呀?jīng)達(dá)到了最大排列方法。因?yàn)槭钦蚁乱粋€(gè)數(shù)，所以我們要找一個(gè)比小卻盡可能大的數(shù)，所以找到。把換到的位置后，后三位仍然是個(gè)降序的排列。 Next Permutation Implement next permutation, which rearranges numbers into the lexicogr...
摘要：題目要求也就是得出所有可能的排列組合結(jié)果解題思路和代碼這題顯然采用遞歸的思路。在這里，我采用實(shí)現(xiàn)隊(duì)列，從隊(duì)列頭獲得上一組的結(jié)果，和當(dāng)前元素結(jié)合之后，將結(jié)果插入到隊(duì)尾。 題目要求 Given a collection of distinct numbers, return all possible permutations. For example, [1,2,3] have the ...
閱讀 2363·2021-11-15 11:37
閱讀 3048·2021-09-01 10:41
閱讀 882·2019-12-27 11:58
閱讀 803·2019-08-30 15:54
閱讀 776·2019-08-30 13:52
閱讀 2987·2019-08-29 12:22
閱讀 1137·2019-08-28 18:27
閱讀 1532·2019-08-26 18:42
