[LeetCode]Orderly Queue

这道题看似有玄机，其实是纯证明题。K = 1的情况非常好解，下面我们证明K >= 2的情况下，我们是可以得到全排列的。为了证明这个结论，我们首先证明可以交换任意两个相邻的字符，如果我们可以交换任意两个相邻的字符，自然可以交换任意两个位置的字符，这点很明显，不过多证明。假设我们有字符串"xx...ab...xx"：

1. 首先我们将其变成"abxx...xx"
2. 因为K >= 2，我们肯定可以取b，append到末尾，变成"axx...xxb"
3. 之后我们在把a append到末尾，变成"xx...xxba"
4. 向左shift，变为"xx..ba..xx"，证明完毕

所以对于K >= 2的情况，我们直接sort即可。时间复杂度，K = 1的情况下O(n^2)，因为我们每次compare也需要O(n)，K >= 2情况下O(n * log n):