首页 > 代码库 > 9.1

9.1

2024-08-01 20:39:01   219人阅读

You are given two sorted arrays, A and B, and A has a large enough buffer at the end
to hold B. Write a method to merge B into A in sorted order.

First let‘s take a look at how merge two arrays works in merge sort algorithm;

public int[] mergeTwoArrays(int[] A, int[] B) {
    　　int Alength = A.length;
    　　int Blength = B.length;
    　　int i = 0;
    　　int j = 0;
    　　int k = 0;
    　　int[] C = new int[Alength + Blength];
　　　　// note integer can not be null; so can not write A[i] != null
    　　while (i < Alength && j < Blength) {
        　　　　if (A[i >= B[j]) {
            　　　　　　C[k++] = B[j++];
        　　　　}
        　　　　else {
            　　　　　　C[k++] = A[i++];
        　　　　}        
    　　}
 　　while (i < Alength) {
            　　　　C[k++] = A[i++];
     　　}
 
     　　while (j < Blength) {
            　　　　C[k++] = B[j++];
     　　}
     　　return C;
}
 Next is merge two sorted list
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
　　if (l1 == null) 
　　　　return l2;
　　if (l2 == null) 
　　　　return l1;
　　ListNode prehead = new ListNode(0);
　　// point to record the current position in the result;
　　ListNode point = prehead;
　　ListNode curr1 = l1;
　　ListNode curr2 = l2;
　　while (curr1 != null && curr2 != null) {
　　　　if (curr1.val < curr2.val) {
　　　　　　ListNode temp = curr1.next;
　　　　　　point.next = curr1;
　　　　　　point = curr1;
　　　　　　curr1 = curr1.next;
　　　　}
　　　　else {
　　　　　　point.next = curr2;
　　　　　　point = curr2;
　　　　　　curr2 = curr2.next;
　　　　}
　　}

　　while (curr1 != null) {
　　　　point.next = curr1;
　　}
　　while (curr2 != null) {
　　　　point.next = curr2;
　　}
　　return prehead;
}
Back to this question, it‘s a special case of merge two sorted array in which array A is much larger than array B. Therefore we don‘t need extra space to store the merged array. The strategy is to compare from then end to the front.
public void merge(int[] A, int m, int[] B, int n) {
　　// two points m and n;
　　while (m > 0 && n > 0) {
　　　　if (A[m - 1] < B[n - 1]) {
　　　　　　A[m + n - 1] = A[m - 1];
　　　　　　m--;
　　　　}
　　　　else {
　　　　　　A[m + n - 1] = A[n - 1];
　　　　　　n--;
　　　　}
　　}

　　while (n > 0) {
　　　　A[m + n - 1] = A[n - 1];
　　　　n--;
　　}
}
 
9.1






























        

            
                
                  
                
                

                    联系

                    我们