【数据结构与算法 | 基础篇】[数组专题]力扣88

简介: 【数据结构与算法 | 基础篇】[数组专题]力扣88

1. 力扣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
  • -109 <= nums1[i], nums2[j] <= 109

进阶:你可以设计实现一个时间复杂度O(m + n) 的算法解决此问题吗?

思路 : 调用Arrays数组工具类中的sort方法.

解1 :

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n;
        int a = 0;
        for(int i = m; i < k; i++) {
            nums1[i] = nums2[a++];
        }
        Arrays.sort(nums1);
    }
}

思路2 : 借助辅助数组

解 :

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n;
        int[] arr = new int[k];
        int o1 = 0;
        int o2 = 0;
        int a = 0;
        while (o1 < m && o2 < n) {
            if(nums1[o1] > nums2[o2]) {
                arr[a++] = nums2[o2++];
            } else {
                arr[a++] = nums1[o1++];
            }
        }
 
        while(o1 < m) {
            arr[a++] = nums1[o1++];
        }
        while(o2 < n) {
            arr[a++] = nums2[o2++];
        }
        for(int i = 0; i < a; i++) {
            nums1[i] = arr[i];
        }
    }
}
相关文章
|
6天前
|
存储 算法 Go
算法学习:数组 vs 链表
算法学习:数组 vs 链表
12 0
|
1天前
|
存储 JavaScript 前端开发
JavaScript中的数组是核心数据结构,用于存储和操作序列数据
【6月更文挑战第22天】JavaScript中的数组是核心数据结构,用于存储和操作序列数据。创建数组可以使用字面量`[]`或`new Array()`。访问元素通过索引,如`myArray[0]`,修改同样如此。常见方法包括:`push()`添加元素至末尾,`pop()`移除末尾元素,`shift()`移除首元素,`unshift()`添加到开头,`join()`连接为字符串,`slice()`提取子数组,`splice()`进行删除、替换,`indexOf()`查找元素位置,`sort()`排序数组。还有其他如`reverse()`、`concat()`等方法。
7 2
|
8天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
8天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
8天前
|
算法 索引 Python
数据结构 数组部分小结
数据结构 数组部分小结
|
8天前
|
C++ Python
二刷力扣--数组
二刷力扣--数组
|
3天前
|
算法
【洛谷 P1003】[NOIP2011 提高组] 铺地毯 题解(数组+贪心算法)
**NOIP2011 提高组问题:铺地毯** 在第一象限的颁奖典礼场地,有$n$张地毯按编号顺序铺设。需找出覆盖特定点$(x, y)$的最上方地毯编号。输入包括地毯坐标和点坐标,输出地毯编号或-1表示未覆盖。 样例:给定3张地毯,点$(2,2)$被第3张地毯覆盖,输出3;另一样例点$(4,5)$未被覆盖,输出-1。 $30\%$数据$n\leq2$,$50\%$数据坐标$\leq100$,$100\%$数据$n\leq10^4$,坐标$\leq10^5$。 解决方法:从下到上遍历地毯,更新覆盖点的地毯编号。 AC代码略。
5 0
|
4天前
|
索引
栈的数组实现
栈的数组实现
4 0
|
10天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
10天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名