增加或减少数组中的序列

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:&nbsp; &nbsp; 1,4,7,9,1,3,5,10,11Sorted:&nbsp; &nbsp;1,1,3,4,5,7,9,10,11&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; └───────┘ └───────┘&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; smallest&nbsp; &nbsp;largest&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ↓&nbsp; &nbsp;↓&nbsp; &nbsp;↓&nbsp; &nbsp; ↓&nbsp; &nbsp; &nbsp;Odd indexesResult:&nbsp; &nbsp;1,7,1,9,3,10,4,11,5&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ↑&nbsp; &nbsp;↑&nbsp; &nbsp;↑&nbsp; &nbsp; ↑&nbsp; &nbsp; ↑&nbsp; Even indexes这样做可以确保解决方案是正确的，假设解决方案是可能的。例如，如果输入是1,1,1,1,2,2,2，您仍然会得到有效的解决方案 ( 1,2,1,2,1,2,1)，而简单的相邻值交换则不会。我会将编码作为练习留给您完成。

Answer 2

我知道您的问题有多个有效输出，但我有同样的想法 @shuki avraham 提到了并且 @Andreas 详细解释了它。所以你对它进行排序，然后在数组中写入最小的然后是最大的数字，依此类推。这是你如何做的：Arrays.sort(arr);&nbsp;for(int i = 0; i < n / 2; i++) {&nbsp; &nbsp; System.out.print(arr[i] + " " + arr[n-i-1] + " ");}if(n % 2 == 1) System.out.print(arr[i]);

Answer 3

按升序对数组进行排序。对于每个偶数索引，从 i=2 开始，交换a[i]和a[i-1]时间和空间复杂度与排序相同

Answer 4

像这样的事情可以解决目的：&nbsp;int[] x = {1, 2, 3, 4, 5, 7, 9, 12, 10, 11, 6, 0};&nbsp; &nbsp; &nbsp; &nbsp; //sort asc&nbsp; &nbsp; &nbsp; &nbsp; Arrays.sort(x);&nbsp; &nbsp; &nbsp; &nbsp; //swap at alternate, take care of odd/even length array&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < x.length - 2;) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int temp = x[i + 1];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x[i + 1] = x[i + 2];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x[i + 2] = temp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i += 2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (i >= x.length) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i--;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(Arrays.toString(x));