Positive-Negative partitioning preserving order

M面经Prepare: Positive-Negative partitioning preserving order - neverlandly - 博客园

Given an array which has n integers,it has both positive and negative integers.

Now you need sort this array in a special way.After that,the negative integers should 

in the front,and the positive integers should in the back.Also the relative position 

should not be changed.  eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.

Time: O(NlogN), space: O(1)/O(logN) depends on iteration/recursion

This can be done in O(nlogn) using divide and conquer scheme. Before starting the algorithm, please see the following observation:

The basic idea of the algorithm is as follows:
1. We recursively 'sort' two smaller arrays of size n/2 (here 'sort' is defined in the question)
2. Then we spend \theta(n) time merging the two sorted smaller arrays with O(1) space complexity.
How to merge?
Suppose the two sorted smaller array is A and B. A1 denotes the negative part of A, and A2 denotes positive part of A. Similarly, B1 denotes the negative part of B, and B2 denotes positive part of B.
2.1. Compute the inverse of A2 (i.e., A2') in \theta(|A2|) time; compute the inverse of B1 (i.e., B1') in \theta(|B1|) time. [See observation; the total time is \theta(n) and space is O(1)]
Thus the array AB (i.e., A1A2B1B2) becomes A1A2'B1'B2.
2.2. Compute the inverse of A2'B1' (i.e., B1A2) in \theta(|A2|) time. [See observation; the total time is \theta(n) and space is O(1)]
Thus the array A1A2'B1'B2 becomes A1B1A2B2. We are done.
Time complexity analysis:
T(n) = 2T(n/2) + \theta(n) = O(nlogn)

 5     public void rearrange(int[] arr) {
 6         if (arr==null || arr.length==0) return;
 7         rearrange(arr, 0, arr.length-1);
 8     }
 9     
10     public void rearrange(int[] arr, int l, int r) {
11         if (l == r) return;
12         int m = (l+r)/2;
13         rearrange(arr, l, m);
14         rearrange(arr, m+1, r);
15         merge(arr, l, m+1, r);
16     }
17     
18     public void merge(int[] arr, int s1, int s2, int e) {
19         int findPos1 = s1, findPos2 = s2;
20         while (findPos1<s2 && arr[findPos1] < 0) findPos1++;
21         while (findPos2<=e && arr[findPos2] < 0) findPos2++;
22         reverse(arr, findPos1, s2-1);
23         reverse(arr, s2, findPos2-1);
24         reverse(arr, findPos1, findPos2-1);
25     }
26     
27     public void reverse(int[] arr, int start, int end) {
28         while (start < end) {
29             int temp = arr[start];
30             arr[start] = arr[end];
31             arr[end] = temp;
32             start++;
33             end--;
34         }
35     }

https://www.geeksforgeeks.org/rearrange-positive-and-negative-numbers/

Approach 2: Optimized Merge Sort
Merge method of standard merge sort algorithm can be modified to solve this problem. While merging two sorted halves say left and right, we need to merge in such a way that negative part of left and right sub-array is copied first followed by positive part of left and right sub-array.

    static void merge(int arr[], int l, int m, int r)

    {

        int i, j, k;

        int n1 = m - l + 1;

        int n2 = r - m;

      

        /* create temp arrays */

        int L[] = new int[n1];

        int R[] = new int[n2];

      

        /* Copy data to temp arrays L[] and R[] */

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

            L[i] = arr[l + i];

        for (j = 0; j < n2; j++)

            R[j] = arr[m + 1 + j];

      

        /* Merge the temp arrays back into arr[l..r]*/

        // Initial index of first subarray

        i = 0; 

          

        // Initial index of second subarray

        j = 0; 

          

        // Initial index of merged subarray

        k = l; 

      

        // Note the order of appearance of elements should

        // be maintained - we copy elements of left subarray

        // first followed by that of right subarray

      

        // copy negative elements of left subarray

        while (i < n1 && L[i] < 0)

            arr[k++] = L[i++];

      

        // copy negative elements of right subarray

        while (j < n2 && R[j] < 0)

            arr[k++] = R[j++];

      

        // copy positive elements of left subarray

        while (i < n1)

            arr[k++] = L[i++];

      

        // copy positive elements of right subarray

        while (j < n2)

            arr[k++] = R[j++];

    }

      

    // 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 - l) / 2;

      

            // Sort first and second halves

            RearrangePosNeg(arr, l, m);

            RearrangePosNeg(arr, m + 1, r);

      

            merge(arr, l, m, r);

        }

    }




Let Ln and Lp denotes the negative part and positive part of left sub-array respectively. Similarly, Rn and Rp denotes the negative and positive part of right sub-array respectively.
Below are the steps to convert [Ln Lp Rn Rp] to [Ln Rn Lp Rp] without using extra space.

1. Reverse Lp and Rn. We get [Lp] -> [Lp'] and [Rn] -> [Rn'] 
    [Ln Lp Rn Rp] -> [Ln Lp’ Rn’ Rp]

2. Reverse [Lp’ Rn’]. We get [Rn Lp].
    [Ln Lp’ Rn’ Rp] -> [Ln Rn Lp Rp]

Time complexity of above solution is O(n log n), O(Log n) space for recursive calls, and no additional data structure.

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

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 - l) / 2;

  

        // Sort first and second halves

        RearrangePosNeg(arr, l, m);

        RearrangePosNeg(arr, m + 1, r);

  

        merge(arr, l, m, r);

    }

}

Approach 1: Modified Insertion Sort

We can modify insertion sort to solve this problem.

Algorithm –

Loop from i = 1 to n - 1.
  a) If the current element is positive, do nothing.
  b) If the current element arr[i] is negative, we 
     insert it into sequence arr[0..i-1] such that 
     all positive elements in arr[0..i-1] are shifted 
     one position to their right and arr[i] is inserted
     at index of first positive element.

Time complexity of above solution is O(n2) and auxiliary space is O(1).

    static void RearrangePosNeg(int arr[], int n)

    {

        int key, j;

        for(int i = 1; i < n; i++)

        {

            key = arr[i];

      

            // if current element is positive

            // do nothing

            if (key > 0)

                continue;

      

            /* if current element is negative,

            shift positive elements of arr[0..i-1],

            to one position to their right */

            j = i - 1;

            while (j >= 0 && arr[j] > 0)

            {

                arr[j + 1] = arr[j];

                j = j - 1;

            }

      

            // Put negative element at its right position

            arr[j + 1] = key;

        }

    }




A simple solution is to use another array. We copy all elements of original array to new array. We then traverse the new array and copy all negative and positive elements back in original array one by one. This approach is discussed here. The problem with this approach is that it uses auxiliary array and we’re not allowed to use any data structure to solve this problem.

https://www.geeksforgeeks.org/move-ve-elements-end-order-extra-space-allowed/

    static void segregateElements(int arr[], int n)

    {

          

        // Create an empty array to store result

        int temp[] = new int[n];

  

        // Traversal array and store +ve element in

        // temp array

        int j = 0; // index of temp

          

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

            if (arr[i] >= 0)

                temp[j++] = arr[i];

  

        // If array contains all positive or all 

        // negative.

        if (j == n || j == 0)

            return;

  

        // Store -ve element in temp array

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

            if (arr[i] < 0)

                temp[j++] = arr[i];

  

        // Copy contents of temp[] to arr[]

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

            arr[i] = temp[i];

    }




https://www.geeksforgeeks.org/rearrange-positive-and-negative-numbers-publish/

An array contains both positive and negative numbers in random order. Rearrange the array elements so that positive and negative numbers are placed alternatively. Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.

For example, if the input array is [-1, 2, -3, 4, 5, 6, -7, 8, 9], then the output should be [9, -7, 8, -3, 5, -1, 2, 4, 6]

    static void rearrange(int arr[], int n)

    {

        // The following few lines are similar to partition

        // process of QuickSort.  The idea is to consider 0

        // as pivot and divide the array around it.

        int i = -1, temp = 0;

        for (int j = 0; j < n; j++)

        {

            if (arr[j] < 0)

            {

                i++;

                temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }

  

        // Now all positive numbers are at end and negative numbers at

        // the beginning of array. Initialize indexes for starting point

        // of positive and negative numbers to be swapped

        int pos = i+1, neg = 0;

  

        // Increment the negative index by 2 and positive index by 1, i.e.,

        // swap every alternate negative number with next positive number

        while (pos < n && neg < pos && arr[neg] < 0)

        {

            temp = arr[neg];

            arr[neg] = arr[pos];

            arr[pos] = temp;

            pos++;

            neg += 2;

        }

    }




Read full article from M面经Prepare: Positive-Negative partitioning preserving order - neverlandly - 博客园