Merge Two Sorted Arrays without additional memory

原创转载请注明出处：http://agilestyle.iteye.com/blog/2361133

 

Question

Merge Two Sorted Arrays into the larger array, given the large array has extra storage. Merge without additional memory

 

Requirements

Long sorted array {1,3,5,0,0,0} (0 means blank spaces), so used length is 3

The short sorted array {2,4}

The expected merged array will be {1,2,3,4,5,0}

Additionally, no additional memory is used

• e.g. declaring a new array is not allowed

Solution

1. Loop from end to beginning.

2. Keep track of two tail index values of two merged arrays.

3. Final-merged-tail position is equal to longTail+ShortTail+1 (both index start from 0!!)

4. If the shortTail is larger than or equal to 0 after merging, adding the remaining values to the merged array

 

package org.fool.java.test;

public class MergeTwoSortedArrays {
    public static void main(String[] args) {
        int[] longArray = {1, 3, 5, 7, 0, 0, 0, 0};
        int used = 4;
        int[] shortArray = {2, 4, 6};

        for (int i : longArray) {
            System.out.print(i + " ");
        }

        System.out.println();

        merge(longArray, shortArray, used);

        for (int i : longArray) {
            System.out.print(i + " ");
        }
    }

    // we passed 3 arguments, the first 2 are the 2 arrays
    // the longUsed is to present how many items are used in the longArray
    // This method returns a int value representing how many valid items to be counted in the merged long array
    private static int merge(int[] longArray, int[] shortArray, int longUsed) {
        int longTail = longUsed - 1;
        int shortTail = shortArray.length - 1;

        // the order is to merge from end to beginning
        while (longTail >= 0 && shortTail >= 0) {
            // check which one in the two arrays should be put at this current tail position
            if (longArray[longTail] > shortArray[shortTail]) {
                // which means at this position, we'd better to put the value int the longArray for the merged array
                longArray[longTail + shortTail + 1] = longArray[longTail];

                // notice the key here for the final index in the merged array
                // longTail + shortTail + 1 will be the final index, thinking that both tail indexes start from 0

                longTail--; // after we put one value in longArray, we need to shift our focus to the left a little
            } else {
                longArray[longTail + shortTail + 1] = shortArray[shortTail];
                shortTail--;
            }
        }

        // case 1, longTail not equal to 0? No problem, they are in position already
        // case 2, shortTail not equal to 0? Need to add element one by one to the final array
        while (shortTail >= 0) {
            longArray[shortTail] = shortArray[shortTail];   // notice the final merging is same as copying
            shortTail--;    // do not forget updating the index
        }

        // return how many used elements in the new merged array
        return shortArray.length + longUsed;
    }
}

Console Output

 

Reference

https://www.youtube.com/watch?v=zYrlYlwkbLo&list=PLlhDxqlV_-vkak9feCSrnjlrnzzzcopSG&index=40