合并排序数组 Ⅱ

题意

合并两个排序的整数数组 A 和 B 变成一个新的数组。

注意事项:你可以假设A具有足够的空间(A数组的大小大于或等于 m + n)去添加B中的元素。 ps:m 表示 A 数组的有效元素个数,n 代表 B 数组的有效元素个数。

样例

给出 A = [1, 2, 3, empty, empty], B = [4, 5]

合并之后 A 将变成 [1,2,3,4,5]

思路

可以正序比较 A 数组与 B 数组的每一位,小的放前,其他的元素依次向后移动,但是依次向后移动这个成本太高了。

所以可以考虑倒序比较,根据数组 A 与数组 B 的最后一个有效位,进行倒序的比较,将大的添加到 A 的最后放即可。

这里要搞清楚的是 A 的最后一个有效位与 A 的最后一位的区别,A 的最后一个有效位是指 A[m-1],而 A 的最后一位是指 A[A.length-1]。

代码实现

class Solution {
    /**
     * @param A: sorted integer array A which has m elements, 
     *           but size of A is m+n
     * @param B: sorted integer array B which has n elements
     * @return: void
     */
    public void mergeSortedArray(int[] A, int m, int[] B, int n) {
        int i = m - 1;
        int j = n - 1;
        int index = m + n -1;
        
        while (i >= 0 && j >=0) {
            if (A[i] > B[j]) {
                A[index--] = A[i--];
            } else {
                A[index--] = B[j--];
            }
        }
        
        while (i >= 0) {
            A[index--] = A[i--];
        }
        
        while (j >= 0) {
            A[index--] = B[j--];
        }
    }
}

原题地址

LintCode:合并排序数组Ⅱ

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏个人随笔

房上的猫:StringBuffer类

一.使用StringBuffer类  StringBuffer类位于java.lang包中,是String类的增强类  步骤:   1.声明StringBuff...

35215
来自专栏C/C++基础

C++抛出异常与传递参数的区别

C++的异常处理机制有3部分组成:try(检查),throw(抛出),catch(捕获)。把需要检查的语句放在try模块中,检查语句发生错误,throw抛出异常...

983
来自专栏我是攻城师

关于Java里面的字符串拼接,你了解多少?

字符串拼接是我们日常开发中很常见的操作,虽然常见,但要是使用不当的的话,很有可能让你的程序处理效率降低一大半,所以我们有必要来重新了解一下Java里面的字符串操...

1653
来自专栏java学习

面试题53(考察求职者对String声明变量在jvm中的存储方法)

(单选题) 1、有如下一段代码,请选择其运行结果() public class StringDemo{ private static final Stri...

2963
来自专栏AILearning

字符串的学习

1> “==”与“equals”的区别 “==”判断的是两个字符串对象在内存中的首地址,就是判断是否是同一个字符串对象; 而equals()判断的是两个字符串对...

1955
来自专栏郭耀华‘s Blog

Java集合框架(四)—— Queue、LinkedList、PriorityQueue

Queue接口   Queue用于模拟了队列这种数据结构,队列通常是指“先进先出”(FIFO)的容器。队列的头部保存在队列中时间最长的元素,队列的尾部保存...

3816
来自专栏无题

链式存储线性表(LinkedList)数据结构解析

LinkedList内部是通过链表来实现的 一、节点分析 LinkedList内部是通过链表来实现的,那么就少不了节点,所以在源码中必然能找到这样一个节点。 ...

3326
来自专栏岑志军的专栏

Swift学习-函数

15210
来自专栏赵俊的Java专栏

删除元素

901
来自专栏三木的博客

Javascript中的数组

数组的定义: var colors = new Array(20); var colors = new Array('red');  // ['red'...

23110

扫码关注云+社区

领取腾讯云代金券