2023-05-21：给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，
并把它加到字符串的末尾。
返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串。
输入：s = "baaca", k = 3。
输出："aaabc"。
答案2023-05-21：
大体过程如下：
1.当 k 大于 1 时，直接将字符串 s 中的字符按照字典序排序，得到排序后的字符串 s'，返回 s'。
2.当 k 等于 1 时，需要使用 DC3 算法对字符串 s 进行处理，得到其所有后缀排名，并找到排名最小的后缀起始位置 minRankIndex。
3.将字符串 s 的前 minRankIndex 个字符移动到字符串末尾，得到新的字符串 s'，返回 s'。
值得注意的是，DC3 算法是一种用于求解后缀数组的算法，可以在 O(n) 的复杂度内计算一个字符串的后缀数组。在本题中，我们需要用到 DC3 算法来寻找字符串 s 所有后缀的排名，以便找到排名最小的后缀起始位置。
对于给定字符串 s 和整数 k，orderlyQueue 函数的时间复杂度和空间复杂度分别如下：
1.当 k > 1 时，时间复杂度为 O(nlogn)，其中 n 是字符串 s 的长度。主要耗时在排序操作中，使用快速排序等算法可以达到 O(nlogn) 的复杂度。空间复杂度也为 O(nlogn)，主要用于存储字符串数组的副本和排序结果。
2.当 k = 1 时，时间复杂度为 O(n)，其中 n 是字符串 s 的长度。时间复杂度主要来自 DC3 算法的实现，该算法可以在 O(n) 的时间复杂度内计算一个字符串的后缀数组。空间复杂度为 O(n)，主要用于存储后缀数组、排名和其他中间变量。
综上所述，orderlyQueue 函数的时间复杂度为 O(nlogn) 或 O(n)，空间复杂度为 O(nlogn) 或 O(n)，具体取决于 k 的值。
go完整代码如下：
代码语言：go复制package main
import (
"fmt"
"sort"
"strings"
)
func orderlyQueue(s string, k int) string {
if k > 1 {
sArr := strings.Split(s, "")
sort.Strings(sArr)
return strings.Join(sArr, "")
} else {
s2 := s s
n := len(s2)
arr := make([]int, n)
for i := 0; i < n; i {
arr[i] = int(s2[i] - 'a' 1)
}
dc3 := NewDC3(arr, 26)
n = n >> 1
minRankIndex := 0
for i := 1; i < n; i {
if dc3.rank[i] < dc3.rank[minRankIndex] {
minRankIndex = i
}
}
return s[minRankIndex:] s[0:minRankIndex]
}
}
// DC3算法实现
// 根据原算法Java代码修改
type DC3 struct {
sa []int
rank []int
}
// NewDC3 构造函数
func NewDC3(nums []int, max int) *DC3 {
dc3 := &DC3{}
dc3.sa = dc3.sa0(nums, max)
dc3.rank = dc3.rank0()
return dc3
}
func (dc3 *DC3) sa0(nums []int, K int) []int {
n := len(nums)
arr := make([]int, n 3)
copy(arr, nums)
return dc3.skew(arr, n, K)
}
func (dc3 *DC3) skew(nums []int, n int, K int) []int {
n0 := (n 2) / 3
n1 := (n 1) / 3
n2 := n / 3
n02 := n0 n2
s12 := make([]int, n02 3)
sa12 := make([]int, n02 3)
for i, j := 0, 0; i < n (n0-n1); i {
if i%3 != 0 {
s12[j] = i
j
}
}
dc3.radixPass(nums, s12, sa12, 2, n02, K)
dc3.radixPass(nums, sa12, s12, 1, n02, K)
dc3.radixPass(nums, s12, sa12, 0, n02, K)
name := 0
c0 := -1
c1 := -1
c2 := -1
for i := 0; i < n02; i {
if nums[sa12[i]] != c0 || nums[sa12[i] 1] != c1 || nums[sa12[i] 2] != c2 {
name
c0 = nums[sa12[i]]
c1 = nums[sa12[i] 1]
c2 = nums[sa12[i] 2]
}
if sa12[i]%3 == 1 {
s12[sa12[i]/3] = name
} else {
s12[sa12[i]/3 n0] = name
}
}
if name < n02 {
sa12 = dc3.skew(s12, n02, name)
for i := 0; i < n02; i {
s12[sa12[i]] = i 1
}
} else {
for i := 0; i < n02; i {
sa12[s12[i]-1] = i
}
}
s0 := make([]int, n0)
sa0 := make([]int, n0)
for i, j := 0, 0; i < n02; i {
if sa12[i] < n0 {
s0[j] = 3 * sa12[i]
j
}
}
dc3.radixPass(nums, s0, sa0, 0, n0, K)
sa := make([]int, n)
for p, t, k := 0, n0-n1, 0; k < n; k {
i := sa12[t]
if i < n0 {
i = i*3 1
} else {
i = (i-n0)*3 2
}
j := sa0[p]
if i < n-1 && j < n-1 {
if nums[i] < nums[j] || (nums[i] == nums[j] && nums[i 1] < nums[j 1]) ||
(nums[i] == nums[j] && nums[i 1] == nums[j 1] && nums[i 2] <= nums[j 2]) {
sa[k] = i
t
if t == n02 {
k
for ; p < n0; p {
sa[k] = sa0[p]
k
}
}
} else {
sa[k] = j
p
if p == n0 {
k
for ; t < n02; t {
i := sa12[t]
if i < n0 {
sa[k] = i*3 1
} else {
sa[k] = (i-n0)*3 2
}
k
}
}
}
} else {
if nums[i] < nums[j] || (nums[i] == nums[j] && nums[i 1] <= nums[j 1]) {
sa[k] = i
t
if t == n02 {
k
for ; p < n0; p {
sa[k] = sa0[p]
k
}
}
} else {
sa[k] = j
p
if p == n0 {
k
for ; t < n02; t {
i := sa12[t]
if i < n0 {
sa[k] = i*3 1
} else {
sa[k] = (i-n0)*3 2
}
k
}
}
}
}
}
return sa
}
func (dc3 *DC3) radixPass(nums []int, input []int, output []int, offset int, n int, k int) {
cnt := make([]int, k 1)
for i := 0; i < n; i {
cnt[nums[input[i] offset]]
}
for i, sum := 0, 0; i < len(cnt); i {
t := cnt[i]
cnt[i] = sum
sum = t
}
for i := 0; i < n; i {
output[cnt[nums[input[i] offset]]] = input[i]
cnt[nums[input[i] offset]]
}
}
func (dc3 *DC3) rank0() []int {
n := len(dc3.sa)
ans := make([]int, n)
for i := 0; i < n; i {
ans[dc3.sa[i]] = i
}
return ans
}
func main() {
s := "baaca"
k := 3
result := orderlyQueue(s, k)
fmt.Println(result)
}
在这里插入图片描述
