LeetCode题:88合并两个有序数组,283移动零,448找到所有数组中消失的数字

本文主要是介绍LeetCode题:88合并两个有序数组,283移动零,448找到所有数组中消失的数字,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

88合并两个有序数组

1、题目要求

2、解题思路

(1)、暴力解法:

(2)、双指针,使用第三数组的解法:

3、代码展示

(1)、暴力解法:

(2)、双指针,使用第三数组的解法:

283移动零

1、题目要求

2、解题思路

双指针法:

3、代码展示

448找到所有数组中消失的数字

1、题目要求

2、解题思路

(1)、使用HashSet集合的方法:

(2)、标记数组下标的方法:

3、代码展示

(1)、使用HashSet集合的方法:

(2)、记录数组下标的方法:

都看到这了,点个赞再走呗,谢谢谢谢谢!!!


88合并两个有序数组

1、题目要求

给你两个按 非递减顺序 排列的整数数组 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 中。

2、解题思路

(1)、暴力解法:

        因为nums1有m+n个元素,m - 1下标后,都是0,我们直接遍历一遍nums2,把nums2的元素全部依次放到nums1中,再对nums1进行整体排序。

(2)、双指针,使用第三数组的解法:

        我们定义一个新的数组,大小为(m + n),遍历一遍这个数组,定义一个nums1和nums2的下标nums1或nums2谁先遍历完,就要把没遍历完的数组剩下全部元素都放进新的数组中如果两个数组都没遍历完,判断nums1和nums2的下标元素谁小,小的放进新的数组中,同时要更新下标小的那一数组下标

3、代码展示

(1)、暴力解法:

时间复杂度:O(N*logN)使用了快速排序

空间复杂度:O(1)

 public void merge(int[] nums1, int m, int[] nums2, int n) {//暴力求法for(int i = 0; i < n; i++) {nums1[m + i] = nums2[i];}Arrays.sort(nums1);}

(2)、双指针,使用第三数组的解法:

时间复杂度:O(N)

空间复杂度:O(1)

public void merge(int[] nums1, int m, int[] nums2, int n) {//定义一个新的数组,这个数组就是我们排完序的数组,把这个数组的元素赋值给数组nums1int[] newNum = new int[m + n];//遍历nums1和nums2数组,比较这两个数组,谁小先放进新的数组中int nums1Index = 0;int nums2Index = 0;for(int index = 0; index < m + n; index++) {if(nums1Index >= m) {//nums1遍历完了,把剩下的nums2全部依次放进newNum中newNum[index] = nums2[nums2Index++];} else if(nums2Index >= n) {//nums2遍历完了,把剩下的nums1全部依次放进newNum中newNum[index] = nums1[nums1Index++];} else if(nums1[nums1Index] < nums2[nums2Index]){//nums1和nums2都没遍历完,要进行比较,谁小把谁先放进newNum中newNum[index] = nums1[nums1Index++];}else{newNum[index] = nums2[nums2Index++];}}//把newNum数组元素全部放进nums1中for(int i = 0; i < n + m; i++) {nums1[i] = newNum[i];}}


283移动零

1、题目要求

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

2、解题思路

双指针法:

时间复杂度:O(N)

空间复杂度:O(1)

        定义i和j下标,i遍历这个数组,同时遍历jj遍历这数组的非零元素,当i遍历完后,j也统计了数组中所有非零元素的个数那么剩下的就都是0元素了,把剩下的0补齐。

3、代码展示

public static void moveZeroes(int[] nums) {//双指针法,复杂度O(N)//先遍历非零元素,非零遍历完后,剩下的都是0int j = 0;for(int i = 0; i < nums.length; i++) {if(nums[i] != 0) {nums[j++] = nums[i];}}//非零遍历完了,剩下的都是0for(int i = j; i < nums.length; i++) {nums[i] = 0;}}


448找到所有数组中消失的数字

1、题目要求

给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。

示例 1:

输入:nums = [4,3,2,7,8,2,3,1]
输出:[5,6]

示例 2:

输入:nums = [1,1]
输出:[2]

2、解题思路

(1)、使用HashSet集合的方法:

时间复杂度:O(N)

空间复杂度:O(N)

         定义一个HashSet遍历一遍数组,把数组的元素都放进set里然后再遍历一遍从1~n(nums.length)的数字,判断set里面有没有这范围的值,没有的话就是缺失的数字,因为题目中的方法要求我们返回链表,所以我们定义一个链表,有缺失的数字就添加到链表中,然后再返回这个链表

(2)、标记数组下标的方法:

时间复杂度:O(N)

空间复杂度:O(1)

        我们的目标是找到缺失数字的下标,知道了缺失数字的下标也能知道缺失的数字,题目之间的关系:数字 = 数字的下标 + 1,如何找到缺失数字的下标呢?

        公式:不是缺失数字的下标 =(数字 - 1)% nums.length,上图,我们可以用这个公式,找到不是缺失数字的下标,然后记录下来他们,上面取了负号的都不是缺失数字的下标,所以这个数组中,4下标和5下标是缺失的数字所以缺失的数字就是5(4+1)和6(5+1)其中我们标记可以取负号,但是这数组中有多个相同的数字,那么多次取负也不一定是负数,我们也可以使用另一种标记的方法:不是缺失的数字就+nums.length第一次遍历完后,所有不是缺失数字都>nums.length,我们再用i遍历一次这个数组的时候,只要是<=nums.length的数字,就是缺失的数字缺失的数字就是i+1把他们添加到list链表上,最后再返回这个链表

3、代码展示

(1)、使用HashSet集合的方法:

 public List<Integer> findDisappearedNumbers(int[] nums) {//set方法List<Integer> list = new LinkedList<>();HashSet<Integer> set = new HashSet<>();//定义一个hashset,把nums的所有元素都放进set里for(int i = 0; i < nums.length; i++) {set.add(nums[i]);}for(int i = 1; i <= nums.length; i++) {if(set.add(i)) {list.add(i);}}return list;}

 

(2)、记录数组下标的方法:

public List<Integer> findDisappearedNumbers(int[] nums) {List<Integer> list = new LinkedList<>();int n = nums.length;for(int x : nums) {//找到x的下标,并记录x下标的值,(x下标值+n)int index = (x - 1) % n;nums[index] += n;}//再次遍历nums,nums元素中,<=n的值就是缺失的数字for(int i = 0; i < n; i++) {if(nums[i] <= n) {list.add(i + 1);}}return list;}


都看到这了,点个赞再走呗,谢谢谢谢谢!!!

这篇关于LeetCode题:88合并两个有序数组,283移动零,448找到所有数组中消失的数字的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/305228

相关文章

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

python3如何找到字典的下标index、获取list中指定元素的位置索引

《python3如何找到字典的下标index、获取list中指定元素的位置索引》:本文主要介绍python3如何找到字典的下标index、获取list中指定元素的位置索引问题,具有很好的参考价值,... 目录enumerate()找到字典的下标 index获取list中指定元素的位置索引总结enumerat

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

Python打印对象所有属性和值的方法小结

《Python打印对象所有属性和值的方法小结》在Python开发过程中,调试代码时经常需要查看对象的当前状态,也就是对象的所有属性和对应的值,然而,Python并没有像PHP的print_r那样直接提... 目录python中打印对象所有属性和值的方法实现步骤1. 使用vars()和pprint()2. 使

Python pip下载包及所有依赖到指定文件夹的步骤说明

《Pythonpip下载包及所有依赖到指定文件夹的步骤说明》为了方便开发和部署,我们常常需要将Python项目所依赖的第三方包导出到本地文件夹中,:本文主要介绍Pythonpip下载包及所有依... 目录步骤说明命令格式示例参数说明离线安装方法注意事项总结要使用pip下载包及其所有依赖到指定文件夹,请按照以

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA