讨论/《排序算法全解析》 - 面试题 10.01. 合并排序的数组/
《排序算法全解析》 - 面试题 10.01. 合并排序的数组
共 3 个回复

Java 100% 不到10行代码, 从后往前比较避免移动元素,不创建任何变量

  public void merge(int[] A, int m, int[] B, int n) {
    while (m >= 1 && n >= 1) {
      A[m + n - 1] = A[m - 1] <= B[n - 1] ? B[--n] : A[--m];
    }

    while (--n >= 0) {
      A[n] = B[n];
    }
  }
class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        """
        Do not return anything, modify A in-place instead.
        """
        k = n + m - 1
        i = m - 1
        j = n - 1

        while i >= 0 and j >= 0:
            if A[i] >= B[j]:
                A[k] = A[i]
                i -= 1
            else:
                A[k] = B[j]
                j -= 1
            k -= 1
        
        while i >= 0:
            A[k] = A[i]
            i -= 1
            k -= 1

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

    }
};