go语言题解LeetCode88合并两个有序数组示例

目录
  • 题目描述
  • 思路分析
  • AC 代码

题目描述

原题链接 :

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

nums1.length == m + n

nums2.length == n

0 <= m, n <= 200

1 <= m + n <= 200

-10^9 <= nums1[i], nums2[j] <= 10^9   进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

思路分析

代码超简单，从后往前看，用两个指针扫描两个数组，边比较边存数，第三个指针指向nums1的末尾存数，存储挪过来的大数。扫描指针移动条件是，该数组有小的数。

退出条件是：nums2的索引到最左边，说明数的比较和移动全部完成。需要注意的是i可能会因为nums2中的数都比较小，一直导致左超限。

AC 代码

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 开了三个指针，从后往前遍历，二个扫描，一个存数
        int i = m-1, j = n-1, k = m+n-1;
        // 循环条件：当nums2检查完，整个工作也完成了。
        while (j >= 0)
        {
            // 注意执行顺序，先判断i >= 0，再判断数大小，否则会报索引超限错误。
            if (i >= 0 && nums1[i] > nums2[j])
            {
                nums1[k] = nums1[i];
                i--;
            }
            // 执行else条件：不满足if中的任意一个条件。
            else
            {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }
    }
}

以上就是go语言题解LeetCode88合并两个有序数组示例的详细内容，更多关于go 合并两个有序数组的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • go语言题解LeetCode1275找出井字棋的获胜者示例

    目录 题目描述 思路分析 AC 代码 题目描述 1275. 找出井字棋的获胜者 - 力扣(LeetCode) A 和 B 在一个 3 x 3 的网格上玩井字棋. 井字棋游戏的规则如下: 玩家轮流将棋子放在空方格 (" ") 上. 第一个玩家 A 总是用 "X" 作为棋子,而第二个玩家 B 总是用 "O" 作为棋子. "X" 和 "O" 只能放在空方格中,而不能放在已经被占用的方格上. 只要有 3 个相同的(

  • go语言题解LeetCode453最小操作次数使数组元素相等

    目录 题目描述 思路分析 AC 代码 小结 遍历数组一次 解题思路 代码 强行找规律 解题思路 代码 题目描述 原题链接 : 453. 最小操作次数使数组元素相等 - 力扣(LeetCode) (leetcode-cn.com) 给你一个长度为 n 的整数数组,每次操作将会使 n - 1 个元素增加 1 .返回让数组所有元素相等的最小操作次数. 示例 1: 输入:nums = [1,2,3] 输出:3 解释: 只需要3次操作(注意每次操作会增加两个元素的值): [1,2,3] => [2,3,3

  • go语言题解LeetCode66加一示例详解

    目录 题目描述 思路分析 AC 代码 小结 JavaScript 66题 代码 python3 循环判断 分析: JAVA解决进位问题 解题思路 代码 题目描述 原题链接 : 66. 加一 给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一. 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字. 你可以假设除了整数 0 之外,这个整数不会以零开头. 示例 1: 输入:digits = [1,2,3] 输出:[1,2,4] 解释:输入数组表示数字 123. 示例 2:

  • Go语言题解LeetCode1266访问所有点的最小时间示例

    目录 题目描述 思路分析 AC 代码 题目描述 1266. 访问所有点的最小时间 - 力扣(LeetCode) 平面上有 n 个点,点的位置用整数坐标表示 points[i] = [xi, yi] .请你计算访问所有这些点需要的 最小时间(以秒为单位). 你需要按照下面的规则在平面上移动: 每一秒内,你可以: 沿水平方向移动一个单位长度,或者 沿竖直方向移动一个单位长度,或者 跨过对角线移动 sqrt(2) 个单位长度(可以看作在一秒内向水平和竖直方向各移动一个单位长度). 必须按照数组中出现的

  • Go语言题解LeetCode35搜索插入位置示例详解

    目录 题目描述 思路分析 AC 代码 总结 优先考虑边界情况 红蓝标记解法 代码 题目描述 原题链接 : 35. 搜索插入位置 - 力扣(LeetCode) (leetcode-cn.com) 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引.如果目标值不存在于数组中,返回它将会被按顺序插入的位置. 请必须使用时间复杂度为 O(log n) 的算法. 示例 1: 输入: nums = [1,3,5,6], target = 5 输出: 2 示例 2: 输入: nums = [1,3

  • Go语言题解LeetCode1260二维网格迁移示例详解

    目录 题目描述 示例 1: 示例 2: 示例 3: 思路分析 AC 代码 题目描述 1260. 二维网格迁移 - 力扣(LeetCode) 给你一个 m 行 n 列的二维网格 grid 和一个整数 k.你需要将 grid 迁移 k 次. 每次「迁移」操作将会引发下述活动: 位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]. 位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]. 位于 grid[m - 1][n - 1] 的元素将会移动到 

  • go语言题解LeetCode88合并两个有序数组示例

    目录 题目描述 思路分析 AC 代码 题目描述 原题链接 : 88. 合并两个有序数组 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目. 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列. 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中.为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素

  • PHP实现合并两个有序数组的方法分析

    本文实例讲述了PHP实现合并两个有序数组的方法.分享给大家供大家参考,具体如下: $arr1 = array(1,2,3,4,5,6,7,8); $arr2 = array(3,4,5,7,9,10); //方法1 function mergeOrderly1($arr1,$arr2){ $i=0;$j=0; $int = array(); while($i<count($arr1) && $j<count($arr2)){ $int[] = $arr1[$i]<$arr

  • Python实现的合并两个有序数组算法示例

    本文实例讲述了Python实现的合并两个有序数组算法.分享给大家供大家参考,具体如下: 思路 按位循环比较两个数组,较小元素的放入新数组,下标加一(注意,较大元素对应的下标不加一),直到某一个下标超过数组长度时退出循环 假设两个源数组的长度不一样,那么假设其中短的数组用完了,即全部放入到新数组中去了,那么长数组中剩下的那一段就可以直接拿来放入到新数组中去了. #coding=utf-8 #合并数据 test1 = [1,2,5,7,9] test2=[2,4,6,8,10,11,34,55] d

  • Python3合并两个有序数组代码实例

    第一种思路,把两个数组合为一个数组然后再排序,问题又回归到冒泡和快排了,没有用到两个数组的有序性.(不好) 第二种思路,循环比较两个有序数组头位元素的大小,并把头元素放到新数组中,从老数组中删掉,直到其中一个数组长度为0.然后再把不为空的老数组中剩下的部分加到新数组的结尾.(好) 第二种思路的排序算法与测试代码如下: def merge_sort(a, b): ret = [] while len(a)>0 and len(b)>0: if a[0] <= b[0]: ret.appen

  • java实现把两个有序数组合并到一个数组的实例

    如下所示: package com.test.sort; public class testMerge { public static void main(String[] args) { int[] a = { 1, 3, 5 }; int[] b = { 2, 3, 4, 7 }; merge m = new merge(); m.method(a, b); } } class merge { public void method(int[] a, int[] b) { int l = a.

  • C语言题解Leetcode56合并区间实例

    目录 解题思路 解题遇到的问题 后续需要总结学习的知识点 解题思路 题目链接 56. 合并区间 本质在于两两做对比,如果两个区间,可以合并,则为结果二维数组中的一员,如果不可合并,则放入结果二维数组,所以根本在于,如何判断两个区间,是可合并,还是不可合并 1.首先将二维数组,按照左端元素进行排序 2.将第一个元素放入结果区间列表 3.如果当前区间的左端元素比结果区间列表最后一个区间右端元素小,则存在包含关系,此时只需更新右端元素即可 (更新为当前区间的右端元素与结果区间的右端元素的最大值) 4.

  • Java实现合并两个有序序列算法示例

    本文实例讲述了Java实现合并两个有序序列算法.分享给大家供大家参考,具体如下: 问题描述 输入:序列A<a0,a1,a2,...aq,aq+1,aq+2,...,ar>,其中a0<a1<...<aq,aq+1<aq+2<...<ar 输出:序列B<b0,b1,...,br>,其中b0<b1<...<br 算法思想 创建一个长度为r的数组R,将A中的序列看作是两个有序序列 B=A<a0,a1,a2,...,aq> C

  • 浅谈JAVA实现选择排序，插入排序，冒泡排序，以及两个有序数组的合并

    浅谈JAVA实现选择排序，插入排序，冒泡排序，以及两个有序数组的合并

    一直到大四才开始写自己的第一篇博客,说来实在有点羞愧.今天写了关于排序的算法题,有插入排序,冒泡排序,选择排序,以下贴上用JAVA实现的代码: public class test5 { public static void print(int []array) //输出数组方法 { for(int i=0;i<array.length;i++) System.out.print(" "+array[i]); } public static void selectsort(int

  • iOS常用算法之两个有序数组合并（要求时间复杂度为0(n)）

    思路: 常规思路: 先将一个数组作为合并后的数组, 然后遍历第二个数组的每项元素, 一一对比, 直到找到合适的, 就插入进去; 简单思路: 设置数组C, 对比A和B数组的首项元素, 找到最小的, 就放入数组C,依次进行下去. 代码如下: - (NSArray *)mergeOrderArrayWithFirstArray: (NSMutableArray *)array1 secondArray: (NSMutableArray *)array2 { // 全为空不处理 if (!array1.

  • Python实现合并两个有序链表的方法示例

    Python实现合并两个有序链表的方法示例

    本文实例讲述了Python实现合并两个有序链表的方法.分享给大家供大家参考,具体如下: 思路:先选出第一个节点,然后遍历两个链表,把小的作为当前节点的下一个节点,一直到其中一个链表遍历完,这时候把另一个链表直接接上就好 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(obj

随机推荐