如何根据第一个值重新排序数组？

Question

我正在解决一个问题“编写一个名为splay的函数，根据第一个值重新组织列表。第一个值称为splaymaster。该函数将重新排列列表，使splaymmaster之前的所有值都小于或等于splaymast，之后的所有值均大于splaymMaster。该函数还返回列表被重新排列。例如，如果列表为[8,15,4,48,26,45,18,29,2,1]，函数将重新排列为[2,1,4,8,26,4518,29，48,15]，并返回值3。您可能无法对列表进行排序。“我似乎遇到的问题是，在上面的例子中，它抱怨html" target="_blank">索引超出边界，这是我的第一个问题。下一个问题是，如果我使用另一个数组，如{90，8，15，4，48，26，45，18，29，2，1}，我得到{1，90，8,15，4,48，26,45，18,29，2}。这是我不正确时的输出。我做错了什么？如何修复它？”？

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static int splay(int[] x) {
        int left = 1;
        int right = x.length;
        int splaymaster = x[0];
        while (left < right) {
            if (x[left] <= splaymaster) {
                left++;
            } else {
                swap(x, left, right);
            }
            swap(x, 0, left - 1);
        }
        return splaymaster;
    }
}

Answer 1

int right = x.length;

数组中最后一个元素的索引是＜code＞x。长度-1，因此索引超出界限。尽管如此，您的算法似乎不正确。仅仅在不同位置交换元件是不够的。如果元素小于splaymaster，则需要将所有元素向上移动一个元素，并将较小的元素插入Splaymastor之前的数组中。我假设可能存在关于解决问题的方法的其他条件，但如果存在，则我从您的问题中不清楚，例如，元素的顺序似乎并不重要，只要splaymaster之前的所有元素都小于或等于它。我还假设您需要就地更改数组，即不允许使用第二个数组。

考虑以下代码：

import java.util.Arrays;

public class SplayTst {

    public static int splay(int x[]) {
        int index = 0;
        int splaymaster = x[0];
        for (int i = 1; i < x.length; i++) {
            if (x[i] <= splaymaster) {
                int temp = x[i];
                for (int j = i; --j >= 0;) {
                    x[j + 1] = x[j];
                }
                x[0] = temp;
                index++;
            }
        }
        return index;
    }

    public static void main(String[] args) {
        int[] test = new int[]{8, 15, 4, 48, 26, 45, 18, 29, 2, 1};
        int ndx = splay(test);
        System.out.println(Arrays.toString(test));
        System.out.println(ndx);
        test = new int[]{90, 8, 15, 4, 48, 26, 45, 18, 29, 2, 1};
        ndx = splay(test);
        System.out.println(Arrays.toString(test));
        System.out.println(ndx);
    }
}

运行上述代码将生成以下输出：

[1, 2, 4, 8, 15, 48, 26, 45, 18, 29]
3
[1, 2, 29, 18, 45, 26, 48, 4, 15, 8, 90]
10

或者，假设您可以使用任何方法来解决问题，请考虑以下使用ArrayList，然后将其转换为数组，然后将所有数组元素复制到原始数组。请注意，用于转换 ArrayList 的单个代码行

如何把一个包含整数的ArrayList转换成原语int数组？

我指的是下面这行代码：

int[] arr = list.stream().mapToInt(i -> i).toArray();

我循环访问原始数组。如果某个元素大于 splaymaster，则将其追加到 ArrayList，否则它将作为 ArrayList 中的第一个元素插入。

import java.util.ArrayList;
import java.util.Arrays;

public class SplayTst {

    public static int splay(int[] x) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(x[0]);
        int index = 0;
        for (int i = 1; i < x.length; i++) {
            if (x[i] <= x[0]) {
                list.add(0, x[i]);
                index++;
            }
            else {
                list.add(x[i]);
            }
        }
        int[] arr = list.stream().mapToInt(i -> i).toArray();
        for (int i = 0; i < x.length; i++) {
            x[i] = arr[i];
        }
        return index;
    }

    public static void main(String[] args) {
        int[] test = new int[]{8, 15, 4, 48, 26, 45, 18, 29, 2, 1};
        int ndx = splay(test);
        System.out.println(Arrays.toString(test));
        System.out.println(ndx);
        test = new int[]{90, 8, 15, 4, 48, 26, 45, 18, 29, 2, 1};
        ndx = splay(test);
        System.out.println(Arrays.toString(test));
        System.out.println(ndx);
    }
}