程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> (每日算法)LeetCode -- Merge Sorted Array (合並有序數組)

(每日算法)LeetCode -- Merge Sorted Array (合並有序數組)

編輯:C++入門知識

(每日算法)LeetCode -- Merge Sorted Array (合並有序數組)





Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m andn respectively.

按照歸並排序的慣性思路,因為歸並排序中給定的是一個數組的兩個區間,所以通常情況下會借助O(n)大小的輔助空間。思路如下:


class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int temp[m+n];
        int i = 0, j = 0, t = 0;
        while(i < m && j < n)
        {
            if(A[i] < B[j])
                temp[t++] = A[i++];
            else
                temp[t++] = B[j++];
        }
        while(i < m)
            temp[t++] = A[i++];
        while(j < n)
            temp[t++] = B[j++];
        while(--t >= 0)
            A[t] = temp[t];
    }
};

但是上述題目給定的條件更加靈活,因此可以采用尾插法,這樣就不再需要輔助空間的開銷,理解上也更加簡潔:


class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int ia = m - 1, ib = n - 1, icur = m + n - 1;
        while(ia >= 0 && ib >= 0)
            A[icur--] = A[ia] > B[ib] ? A[ia--] : B[ib--];
        while(ib >=0)
            A[icur--] = B[ib--];
    }
};


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved