題目來(lái)源
將1-n整型數(shù)字以字典序排序容贝。
我想著先轉(zhuǎn)換為string伞租，然后排序淹接，然后再轉(zhuǎn)為int十性，代碼如下：
class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<string> resString(n, "");
for (int i=1; i<=n; i++)
resString[i-1] = to_string(i);
sort(resString.begin(), resString.end());
vector<int> res;
for (auto item : resString)
res.push_back(atoi(item.c_str()));
return res;
}
};
然后結(jié)果不出意料的超時(shí)了。然后我想著是不是可以用排序算法塑悼，不過(guò)自己來(lái)設(shè)定排序規(guī)則劲适。
看了下討論區(qū)，就是不斷的找下一個(gè)元素厢蒜，代碼如下：
class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int> res;
if (n < 1)
return res;
int cur = 1;
res.push_back(cur);
for (int i=1; i<n; i++) {
if (cur * 10 <= n)
cur = cur * 10;
else if (cur % 10 != 9 && cur + 1 <= n)
cur++;
else {
//這里注意一下霞势，假如n=13，那么當(dāng)cur=13的時(shí)候斑鸦，下一個(gè)應(yīng)該是2愕贡。
while ((cur / 10) % 10 == 9)
cur /= 10;
cur = cur / 10 + 1;
}
res.push_back(cur);
}
return res;
}
};
