q****m
发帖数: 177 | 1 我先写的那个 next permutation, 然后call 它 k次， 结果超时。
有什么好的方法吗？
谢谢 | l*****a
发帖数: 14598 | 2 那说明你的next permutation没写好
我就这么做的，没超时
【在 q****m 的大作中提到】
: 我先写的那个 next permutation, 然后call 它 k次， 结果超时。
: 有什么好的方法吗？
: 谢谢
| q****m
发帖数: 177 | 3 能把你的贴一下吗？ 这是我的code.
class Solution {
public:
void nextPermutation(vector &num) {
int i = num.size() - 1;
while(i >= 1 && num[i - 1] >= num[i])
{
--i;
}
if(i == 0)
{
int l = 0, r = num.size() -1 ;
while(l <= r)
{
swap(num[l], num[r]);
++l;
--r;
}
return;
}
int left = i, right = num.size() - 1, target = num[i - 1];
while(left < right)
{
int mid = (left + right) / 2;
if(num[mid] > target)
{
left = mid + 1;
}
else
{
right = mid;
}
}
int tmp = left;
if(num[tmp] <= target)
{
tmp = left - 1;
}
swap(num[i - 1], num[tmp]);
left = i, right = num.size() - 1;
while(left <= right)
{
swap(num[left], num[right]);
++left;
--right;
}
}
string getPermutation(int n, int k) {
vectorv(n, 0);
for(int i = 1; i <= n; ++i)
{
v[i - 1] = i;
}
for(int i = 2; i <= k; ++i)
{
nextPermutation(v);
}
string s;
for(int i = 0; i < n; ++i)
{
s.append(1, v[i] + '0');
}
return s;
}
};
【在 l*****a 的大作中提到】
: 那说明你的next permutation没写好
: 我就这么做的，没超时
| l*****a
发帖数: 14598 | 4 经典算法，查得到吧
扫了一眼，你中间插了一段两分，是想干吗
【在 q****m 的大作中提到】
: 能把你的贴一下吗？ 这是我的code.
: class Solution {
: public:
: void nextPermutation(vector &num) {
: int i = num.size() - 1;
:
: while(i >= 1 && num[i - 1] >= num[i])
: {
: --i;
: }
| l*****a
发帖数: 14598 | 5 不是有序的吧？
直接loop就可以啊
exist, | o*****n
发帖数: 189 | 6 这道题不需要算permutation.
直接找下一个数. 关键是找出最大位.
比如, 1365 -> 1536, 12837 -> 12873 |
|
