专栏首页刷题笔记【LeetCode程序员面试金典】面试题 10.01. Sorted Merge LCCI

【LeetCode程序员面试金典】面试题 10.01. Sorted Merge LCCI

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

Initially the number of elements in A and B are m and n respectively.

Example:

Input: A = [1,2,3,0,0,0], m = 3 B = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/sorted-merge-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

双指针

A的后面是空的,所以可以换一个思路,从最后一个值开始判断最大值存入

从后往前遍历,就不会被内存空间所限制

class Solution {
    public void merge(int[] A, int m, int[] B, int n) {
        int a=m-1;
        int b=n-1;
        for(int i=m+n-1;i>=0;i--){
            if(b<0||(a>=0&&A[a]>B[b])){
                A[i]=A[a];
                a--;
            }else{
                A[i]=B[b];
                b--;
            }
        }
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1061 判断题 (15 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【未完成】1068 万绿丛中一点红 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 2-5 修理牧场 (35 分)【优先队列】

    农夫要修理牧场的一段栅栏,他测量了栅栏,发现需要N块木头,每块木头长度为整数L​i​​个长度单位,于是他购买了一条很长的、能锯成N块的木头,即该木头的长度是L​...

    韩旭051
  • URAL 2040 Palindromes and Super Abilities 2(回文树)

    Palindromes and Super Abilities 2 Time Limit: 1MS Memory Limit: 102400KB ...

    ShenduCC
  • Super Pow:如何高效进行模幂运算

    今天来聊一道与数学运算有关的算法题目,LeetCode 372 题 Super Pow,让你进行巨大的幂运算,然后求余数。

    帅地
  • 当七夕遇上算法竞赛

      七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕,于是他们决定去T...

    ACM算法日常
  • hdu1030

    @坤的
  • 675. Cut Off Trees for Golf Event

    You are asked to cut off all the trees in this forest in the order of tree’s he...

    用户1147447
  • 2-5 修理牧场 (35 分)【优先队列】

    农夫要修理牧场的一段栅栏,他测量了栅栏,发现需要N块木头,每块木头长度为整数L​i​​个长度单位,于是他购买了一条很长的、能锯成N块的木头,即该木头的长度是L​...

    韩旭051
  • Data Structure_Visualization

    选择排序很简单,遍历所有元素,查看一下他们的之后最小的元素和当前元素交换即可。模板函数使用上面的swing模板。为了更清楚显示出排序的过程,可以用不同颜色代表排...

    西红柿炒鸡蛋

扫码关注云+社区

领取腾讯云代金券