LeetCode-Merge Sorted Array

我不是女神ヾ 2022-08-06 13:03 184阅读 0赞

题目：

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 mand n respectively.

一般的归并方法：

public void merge(int A[], int m, int B[], int n) {
            int C[] = new int[A.length];
    		int i = 0, j = 0, k = 0;
    		while (i < m && j < n) {
    			if (A[i] <= B[j]) {
    				C[k++] = A[i++];
    			} else {
    				C[k++] = B[j++];
    			}
    		}
    		while (i < m) {
    			C[k++] = A[i++];
    		}
    		while (j < n) {
    			C[k++] = B[j++];
    		}
    		System.arraycopy(C, 0, A, 0, m+n);
        }

明显这种方法的空间耗费比较大，并且最后还进行了数组的拷贝，也是比较耗时的！换个角度思考，为什么要从头开始比较归并呢？为什么不从数组尾部开始比较归并呢？见如下代码，空间耗费更小，时间更短：

int i = m-1, j = n-1, k = m+n-1;
    		while (i >= 0 && j >= 0) {
    			if (A[i] >= B[j]) {
    				A[k--] = A[i--];
    			} else {
    				A[k--] = B[j--];
    			}
    		}
    		while (i >= 0) {
    			A[k--] = A[i--];
    		}
    		while (j >= 0) {
    			A[k--] = B[j--];
    		}

速度可媲美c++

发表评论取消回复

表情：

评论列表（有 0 条评论，184人围观）

还没有评论，来说两句吧...

相关阅读

相关 Arrays.sort排序算法

ava默认的排序算法及思路 List.sort() 还是 Collections.sort底层的排序都是调用了Arrays.sort()方法 Arrays.sort...

一时失言乱红尘/ 2024年04月18日 19:52/ 0 赞/ 98 阅读

相关 Merge Sorted Array--LeetCode

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

淩亂°似流年/ 2022年08月07日 13:41/ 0 赞/ 21 阅读

相关 LeetCode-Merge Sorted Array

题目： Given two sorted integer arrays A and B, merge B into A as one sorted array. Note:

我不是女神ヾ/ 2022年08月06日 13:03/ 0 赞/ 185 阅读

相关 Leetcode: Merge Sorted Array

题目： Given two sorted integer arrays A and B, merge B into A as one sorted array. Note

心已赠人/ 2022年08月05日 15:11/ 0 赞/ 25 阅读

相关 JAVA Arrays.sort()和Collectons.sort() 原理分析

今天终于答辩结束，I’M FREEDOM!!! ^—^ 首先Collections内部也是使用Arrays的sort实现的，因此着重分析Arrays类内的sort是如何实现的

墨蓝/ 2022年06月08日 11:24/ 0 赞/ 199 阅读

相关 88. Merge Sorted Array

[88. Merge Sorted Array][] Given two sorted integer arrays nums1 and nums2, merge nums2

落日映苍穹つ/ 2022年06月08日 06:17/ 0 赞/ 155 阅读

相关 JavaScript温故知新----Array.sort()

默认情况下，sort()方法会从小到大的排列数组中的每一项，为了实现排序， sort()方法会调用每个数组项的 toString()转型方法，然后比较得到的字符串，以确定如何排

淩亂°似流年/ 2022年06月07日 03:13/ 0 赞/ 225 阅读

相关 Collections.sort()和Arrays.sort()排序算法选择

源码位置: [点击打开链接][Link 1] [点击打开链接][Link 2] Arrays.sort() 先来看看`Arrays.sort();`，点进去这个方法会

忘是亡心i/ 2022年05月29日 07:49/ 0 赞/ 203 阅读

相关 Arrays sort排序

Arrays.sort默认是升序，如果我们需要降序排列数组？ Arrays.sort(distances);——升序 Arrays.sort(distances, Coll

缺乏、安全感/ 2022年04月23日 13:52/ 0 赞/ 281 阅读

相关 905 sort-array-by-parity

class Solution: def sortArrayByParity(self, A: List[int]) -> List[int]:

港控/mmm°/ 2021年12月14日 09:09/ 0 赞/ 241 阅读