找到可实现的字典序最小序列

Question

这是问题陈述

Given a sequence of n integers arr, determine the lexicographically smallest sequence which may be obtained from it after performing at most k element swaps, each involving a pair of consecutive elements in the sequence.
Note: A list x is lexicographically smaller than a different equal-length list y if and only if, for the earliest index at which the two lists differ, x's element at that index is smaller than y's element at that index.

我正试图根据上述注释理解“按字典顺序排列更小”这一短语的含义。据我了解它的英文含义，我们基本上是在谈论字典顺序。让我用一个例子来解释我的问题。

举个例子

Example 1
n = 3
k = 2
arr = [5, 3, 1]
output = [1, 5, 3]
We can swap the 2nd and 3rd elements, followed by the 1st and 2nd elements, to end up with the sequence [1, 5, 3]. This is the lexicographically smallest sequence achievable after at most 2 swaps.

上面的例子附带了问题陈述。但是字典上最小的序列不是 [1, 3 , 5] 而不是提供的答案（输出） [1, 4, 3] 吗？

这是另一个

Example 2
n = 5
k = 3
arr = [8, 9, 11, 2, 1]
output = [2, 8, 9, 11, 1]
We can swap [11, 2], followed by [9, 2], then [8, 2].

同样，在这种情况下我能看到的答案是 [1, 2, 8, 11, 9]（经过三次交换），这是最小的字典序盟友，提供的答案是输出 = [2, 8 , 9, 11, 1].

我是否错误地阅读了问题陈述？

Answer 1

问题陈述说，我们最多可以对过程中的连续元素进行 k 次交换，以获得字典序最小的序列。下面的解释可以帮助我们更好地理解它。 [注意：请记住，您只能交换连续的元素]

n = 3
k = 2
arr = [5, 3, 1]
输出 = [1, 5, 3]
方法：
交换 1: 交换 3 和 1 (3<->1) ====> [5,1,3]
交换 2: 交换 5 和 1 (5<->1) ====> [1,5,3] #RESULT
n = 5
k = 3
arr = [8, 9, 11, 2, 1]
输出 = [2, 8, 9, 11, 1]
方法：
交换 1: 交换 11 和 2 (11<->2) ===> [8, 9, 2, 11, 1]
交换 2: 交换 9 和 2 (9<->2) ===> [8, 2, 9, 11, 1]
交换 2: 交换 8 和 2 (9<->2) ===> [2, 8, 9, 11, 1] #RESULT

所以，你永远无法通过连续元素的 3 次交换得到 [1, 2, 8, 11, 9]。 2 是您可以移动到第一个索引的最小元素，最多 3 次连续元素交换，但是如果 k=4，那么我们可以将 1 移到第一个位置。

因此，您缺少的是规则是您最多可以交换 k 个元素，但您交换的元素应该彼此连续。

找到可实现的字典序最小序列

Find the lexicographically smallest sequence achievable

javascript

arrays

algorithm

lexicographic