增加或减少数组中的序列

Question

我有一个元素数组需要根据以下规则打印出来：

ai1 <= ai2 >= ai3 <= ai4 >= ai5 <= ai6

输入列表=30、12、49、6、10、50、13

预期输出 = [10, 6, 30, 12, 49, 13, 50]

请建议我解决这个问题的方法。这是我尝试过的。

      Arrays.sort(arr);

        for(i=2;i<n;i++)

        {

            if(i%2==0)

            {

                int temp =arr[i-1];

                arr[i-1]=arr[i];

                arr[i] = temp;

            }

        }

        System.out.println("\n");

        for(i=0;i<n;i++)

还帮助我找到给定方法的时间复杂度和空间复杂度。

Answer 1

规则似乎是奇数索引 (1, 3, 5, ...) 处的值必须大于相邻索引处的值，例如，索引 5 处的值必须大于索引 4 和 6 处的值。

实现此目的的最简单方法是将最小值放在偶数索引处，将最大值放在奇数索引处。要将值拆分为最小值和最大值，请先对值进行排序。

例子：

Input:    1,4,7,9,1,3,5,10,11

Sorted:   1,1,3,4,5,7,9,10,11

          └───────┘ └───────┘

          smallest   largest

            ↓   ↓   ↓    ↓     Odd indexes

Result:   1,7,1,9,3,10,4,11,5

          ↑   ↑   ↑    ↑    ↑  Even indexes

这样做可以确保解决方案是正确的，假设解决方案是可能的。例如，如果输入是1,1,1,1,2,2,2，您仍然会得到有效的解决方案 ( 1,2,1,2,1,2,1)，而简单的相邻值交换则不会。

我会将编码作为练习留给您完成。

Answer 2

我知道您的问题有多个有效输出，但我有同样的想法 @shuki avraham 提到了并且 @Andreas 详细解释了它。

所以你对它进行排序，然后在数组中写入最小的然后是最大的数字，依此类推。这是你如何做的：

Arrays.sort(arr); 

for(int i = 0; i < n / 2; i++) {

    System.out.print(arr[i] + " " + arr[n-i-1] + " ");

}

if(n % 2 == 1) System.out.print(arr[i]);

Answer 3

1. 按升序对数组进行排序。

2. 对于每个偶数索引，从 i=2 开始，交换a[i]和a[i-1]

3. 时间和空间复杂度与排序相同

Answer 4

像这样的事情可以解决目的：

 int[] x = {1, 2, 3, 4, 5, 7, 9, 12, 10, 11, 6, 0};

        //sort asc

        Arrays.sort(x);

        //swap at alternate, take care of odd/even length array

        for (int i = 0; i < x.length - 2;) {

            int temp = x[i + 1];

            x[i + 1] = x[i + 2];

            x[i + 2] = temp;

            i += 2;

            if (i >= x.length) {

                i--;

            }

        }

        System.out.println(Arrays.toString(x));