本文主要是介绍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遍历这个数组,同时遍历j,j遍历这数组的非零元素,当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找到所有数组中消失的数字的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!