标题是不言自明的,但这里有几个例子:
- aabbcc -> abcabc
- abcabc -> cbabac
- cbacbaca -> bcacacba
我认为 std::random_shuffle(myString.begin(), myString.end())
会很有趣,因为它永远不会通过不同的调用进行相同的重新排序,但它需要当生成的字符串在连续位置没有相似字符时循环。是否有更合乎逻辑的方式来进行重新排序,或任何其他功能做类似的事情?
注意:重新排序不需要随机进行。只要相同的字符不在连续的位置,就可以使用排序功能。
更新:如评论中所述...是的,random_shuffle 可以连续多次返回相同的字符串顺序。假设采用上述方法,next_permutation
会更合适。
最佳答案
首先请注意,解决方案并不总是存在。当且仅当出现次数最多的元素不超过 (n+1)/2
时,它才存在。
因此很容易检查解是否存在。如果它存在,那么下面的代码将找到它
bool cmpBySecond(const std::pair<char, int>& a, const std::pair<char, int>& b) {
if (a.second == b.second) return a.first < b.first;
return a.second < b.second;
}
std::string reorder(const std::string& input) {
std::map<char, int> cnt;
for (auto& c: input) cnt[c]++;
auto items = std::vector<std::pair<char, int>>(cnt.begin(), cnt.end());
std::sort(items.begin(), items.end(), cmpBySecond);
std::reverse(items.begin(), items.end());
// now we have chars with occurencies counts in descending order
std::string result(input);
int pos = 0;
for (auto& it: items) {
char c = it.first;
int times = it.second;
for (int i = 0; i < times; ++i) {
result[pos] = c;
pos += 2;
if (pos >= result.size()) pos = 1;
}
}
return result;
}
超越它的想法是分布最频繁的元素,然后用其余元素填补空白。
还有一些测试的相同代码 here .
关于c++ - 将字符串重新排序为没有连续相同字符的字符串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36816064/