时间戳

首页 > 解决方案 > 将正数放在负数之前

java - 将正数放在负数之前

问题描述

所以我有这个代码，我在互联网上找到了一个负数和正数数组并重新排列数组，所以所有负数都在正数之前。但是每个数字的出现位置必须保持不变。因此，例如，如果我有-2 5 -9 .....，在有组织的数组中-2仍然必须是负数的第一个数字，并且必须是负数的第二个，也必须是正数的第一个数。-95

例子：

Input: {1,7,-5,9,-12,15,-6,-8}
Output:{-5,-12,-6,-8,1,7,9,15}

所以代码工作正常，但我想做的是改变它，使正数出现在负数之前。

例子：

Input: {1,7,-5,9,-12,15,-6,-8}
Output:{1,7,9,15,-5,-12,-6,-8}

这是代码，如果你能帮助我，我知道它不是很复杂，但我无法弄清楚。

// Java program to Rearrange positive and negative
// numbers in a array
public class Rearrangement {
    /* Function to print an array */
    static void printArray(int[] A, int size) {
        for (int i = 0; i < size; i++)
            System.out.print(A[i] + " ");
        System.out.println("");
    }

    /* Function to reverse an array. An array can be
    reversed in O(n) time and O(1) space. */
    static void reverse(int[] arr, int l, int r) {
        if (l < r) {
            arr = swap(arr, l, r);
            reverse(arr, ++l, --r);
        }
    }

    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    static void merge(int[] arr, int l, int m, int r) {
        int i = l; // Initial index of 1st subarray
        int j = m + 1; // Initial index of IInd

        while (i <= m && arr[i] < 0)
            i++;
        // arr[i..m] is positive
        while (j <= r && arr[j] < 0)
            j++;
        // arr[j..r] is positive

        // reverse positive part of
        // left sub-array (arr[i..m])
        reverse(arr, i, m);

        // reverse negative part of
        // right sub-array (arr[m+1..j-1])
        reverse(arr, m + 1, j - 1);

        // reverse arr[i..j-1]
        reverse(arr, i, j - 1);
    }

    // Function to Rearrange positive and negative
    // numbers in a array
    static void RearrangePosNeg(int[] arr, int l, int r) {
        if (l < r) {
            // Same as (l+r)/2, but avoids overflow for
            // large l and h
            int m = (l + r) / 2;

            // Sort first and second halves
            RearrangePosNeg(arr, l, m);
            RearrangePosNeg(arr, m + 1, r);

            merge(arr, l, m, r);
        }
    }

    static int[] swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {1, 7, -5, 9, -12, 15, -6, -8};
        int arr_size = arr.length;
        RearrangePosNeg(arr, 0, arr_size - 1);
        printArray(arr, arr_size);
    }
}

标签： javaarrayssortingrecursion

解决方案

现有的解决方案可以很容易地通过向Predicate<Integer>方法添加参数来参数化rearrangePosNeg，merge并且根据这个参数，正值或负值将被放置在数组的开头：

static void rearrangePosNeg(int[] arr, int l, int r, Predicate<Integer> p) {
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for large l and r
        int m = l - (l - r)/2;

        // Sort first and second halves
        rearrangePosNeg(arr, l, m, p);
        rearrangePosNeg(arr, m + 1, r, p);

        merge(arr, l, m, r, p);
    }
}

static void merge(int[] arr, int l, int m, int r, Predicate<Integer> p) {
    int i = l; // Initial index of 1st subarray
    int j = m + 1; // Initial index of IInd

    while (i <= m && p.test(arr[i])) i++;
    while (j <= r && p.test(arr[j])) j++;

    reverse(arr, i, m);

    reverse(arr, m + 1, j - 1);

    reverse(arr, i, j - 1);
}

然后rearrangePosNeg可以调用该方法：

int[] arr = {1,7,-5,9,-12,15,-6,-8};
int arr_size = arr.length;
rearrangePosNeg(arr, 0, arr_size - 1, (x) -> x > 0); // put positives first
printArray(arr, arr_size);

输出：

1 7 9 15 -5 -12 -6 -8

此外，使用新数组和几个索引的更简单的迭代解决方案是可能的：

static int[] rearrange(int[] arr, Predicate<Integer> p) {
    int n = arr.length;
    int[] rearranged = new int[n--];

    for (int i = 0, iFirst = 0, iLast = n; i <= n; i++) {
        if (p.test(arr[i])) {
            rearranged[iFirst++] = arr[i]; // copying by condition to the head
        }
        if (!p.test(arr[n - i])) {
            rearranged[iLast--] = arr[n - i]; // copying opposite to the tail
        }
    }
    return rearranged;
}

测试：

int[] arr = {1,7,-5,9,-12,15,-6,-8};

System.out.println("iterative: " +  Arrays.toString(rearrange(arr, (x) -> x > 0)));

输出：

iterative: [1, 7, 9, 15, -5, -12, -6, -8]

更新

没有Predicate参数，merge函数中的条件需要反转：

static void rearrangePosNeg(int[] arr, int l, int r) {
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for large l and r
        int m = l - (l - r)/2;

        // Sort first and second halves
        rearrangePosNeg(arr, l, m);
        rearrangePosNeg(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

static void merge(int[] arr, int l, int m, int r) {
    int i = l; // Initial index of 1st subarray
    int j = m + 1; // Initial index of IInd

    while (i <= m && arr[i] > 0) i++;
    while (j <= r && arr[j] > 0) j++;

    reverse(arr, i, m);

    reverse(arr, m + 1, j - 1);

    reverse(arr, i, j - 1);
}

推荐阅读