考虑到问题标准，是否有比冒泡排序更有效的排序此数组的形式?

Question

我在HackerRank上练习了更多的问题，我遇到了一个叫做"新年混乱"的问题。基本上，前提是对数组进行排序并计算所做的开关。问题是不允许进行超过 2 个开关的数字。BubbleSort通过了前几个测试，但其余测试超时。是否有更有效的数组排序算法仍然考虑开关的数量？我尝试了合并排序和快速排序，但在像这样划分数组时很难跟踪开关。

问题提示： 今天是元旦，每个人都在排队等待仙境过山车之旅！有很多人排队，每个人都戴着一张贴纸，表明他们在队列中的初始位置。初始位置从行的前部递增到后部。

队列中的任何人都可以贿赂直接在他们面前的人交换位置。如果两个人交换位置，他们仍然会佩戴相同的贴纸，表示他们原来排队的位置。一个人最多可以贿赂另外两个人。例如，如果 n = 8 并且人员 5 贿赂人员 4，则队列将如下所示：{1， 2， 3， 5， 4， 6， 7， 8}。

对这个混乱的队列着迷，你决定你必须知道使队列进入当前状态的最低贿赂数量！

public class LineBribing {
static int[] replace(int[] q, int i, int n) {
int temp = q[i];
q[i] = q[n];
q[n] = temp;
return q;
}
static void minimumBribes(int[] q) {
int count = 0;
for (int i = 0; i < q.length - 1; i++) {
if (q[i] > i + 3 || q[i] < i - 1) {
System.out.println("Too chaotic");
return;
}
if (q[i] > q[i + 1]) {
count++;
replace(q, i, i + 1);
i = 0;
}
}
System.out.println(count);
}
public static void main(String[] args) {
int[] test = {1, 2, 5, 3, 4, 7, 8, 6};
int[] test2 = {1, 2, 5, 3, 7, 8, 6, 4};
minimumBribes(test);
minimumBribes(test2);
}
}

给定 main 方法中的输入，测试 1 的输出应为 4(索引 = 3 时的开关：5、3 | 5、索引 = 4 时的 4 | 8、索引 = q.length -1 | 7、6 的索引 = q.length - 2(和测试 2 的"太混沌"(因为 5 是 2 个开关远离其初始位置>

(

Answer 1

我认为这个问题不需要对数组进行排序。你只需要计算超过一个人的人数。请注意：

• 一个人最多可以贿赂 2 个不同的人
• 一个人可以贿赂在他面前的人 因此，您应该先判断任何人贿赂超过2人。然后数超车人数。

我的Java代码是这样的：

int ans = 0;
for (int i = q.length - 1; i >= 0; i--) {
if (q[i] - (i + 1) > 2) {
System.out.println("Too chaotic");
return;
}
for (int j = Math.max(0, q[i] - 2); j < i; j++) {
if (q[j] > q[i]) {
ans++;
}
}
}
System.out.println(ans);

Answer 2

这是我针对此问题的java 7代码。

public static void minimumBribes(List<Integer> q) {
int count = 0;
for(int i = q.size()-1; i >= 0; i--){
if(q.get(i) != (i+1)){
if((i+1) == q.get(i-1) && (i - 1) >= 0){
Collections.swap(q, i-1, i);
count++;              
}else if((i+1) == q.get(i-2) && (i-2) >= 0){
Collections.swap(q, i-2, i-1);
Collections.swap(q, i-1, i);
count+=2;          
}else{
System.out.println("Too chaotic");
return;
}
} 
}
System.out.println(count);
}