当前位置:网站首页>【C语言】LeetCode26.删除有序数组中的重复项&&LeetCode88.合并两个有序数组
【C语言】LeetCode26.删除有序数组中的重复项&&LeetCode88.合并两个有序数组
2022-08-02 05:04:00 【阿亮joy.】
目录
描述:
给你一个升序排列的数组nums ,请你原地删除重复出现的元素,使每个元素只出现一次 ,返回删除后数组的新长度。元素的相对顺序应该保持一致 。
不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例1
输入:
nums = [1,1,2]
输出:
2, nums = [1,2,_]
解释:
函数应该返回新的长度2 ,并且原数组nums的前两个元素被修改为1, 2 。不需要考虑数组中超出新长度后面的元素。
示例2
输入:
nums = [0,0,1,1,1,2,2,3,3,4]
输出:
5, nums = [0,1,2,3,4]
解释:
函数应该返回新的长度5 ,并且原数组nums的前五个元素被修改为0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
思路一:
int removeDuplicates(int* nums, int numsSize){
if (numsSize == 0)
return 0;
int i = 0, j = 1;
int dst = 0;
while (j < numsSize)
{
if (nums[i] == nums[j])
{
j++;
}
else
{
nums[dst] = nums[i];
dst++;
i = j;
j++;
}
}
nums[dst] = nums[i];
dst++;
return dst;
}
思路二:
int removeDuplicates(int* nums, int numsSize)
{
if (numsSize == 0)
return 0;
int fast = 1, slow = 1;
while (fast < numsSize)
{
if (nums[fast] != nums[fast - 1])
{
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
分析:时间复杂度为O(N),空间复杂度为O(1)。
合并两个有序数组
说明:
给你两个按非递减顺序排列的整数数组nums1和nums2,另有两个整数m和n ,分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中,使合并后的数组同样按非递减顺序排列。
注意:
最终,合并后数组不应由函数返回,而是存储在数组nums1中。为了应对这种情况,nums1 的初始长度为m+n,其中前m个元素表示应合并的元素,后n个元素为 0 ,应忽略。nums2 的长度为n。
示例
输入:
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] 。
进阶:
你可以设计实现一个时间复杂度为
O(m + n)
的算法解决此问题吗?
思路一:
最简单直观的方法就是,先将数组nums2放进数组nums1的尾部,然后再对数组num1进行快速排序。
int cmp(int* a, int* b)
{
return *a - *b;
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
for (int i = 0; i < n; i++)
{
nums1[m + i] = nums2[i];
}
qsort(nums1, m + n, sizeof(int), cmp);
}
分析:时间复杂度:O((m+n)log(m+n)),空间复杂度:O(log(m+n)。
思路二:
开辟一个新的数组,先将小的元素存放进去。当其中一个数组的元素存放完,再将另一个数组的元素存放进去,最后将该数组的数据拷贝给目标数组。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
int i = 0, j = 0, k = 0;
int* nums = (int*)malloc(sizeof(int) * (m + n));
//i为nums的下标,j为nums1的下标,k为nums2的下标
while (j < m && k < n)
{
if (nums1[j] < nums2[k])
{
nums[i] = nums1[j];
i++;
j++;
}
else
{
nums[i] = nums2[k];
i++;
k++;
}
}
while (j < m)
{
nums[i] = nums1[j];
i++;
j++;
}
while (k < n)
{
nums[i] = nums2[k];
i++;
k++;
}
memcpy(nums1, nums, sizeof(int) * (m + n));
}
分析:时间复杂度为O(m+n),空间复杂度为O(m+n)。
思路三:
不开辟额外的空间,直接先将较大的元素存放到数组nums的后面,直到其中一个数组存放完。如果数组nums1先存放完,那么数组nums2中还有元素需要存放到数组nums1的前面;如果数组nums2先存放完,那么现在的数组num1就是所求的数组。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
int end = m + n - 1, end1 = m - 1, end2 = n - 1;
while (end1 >= 0 && end2 >= 0)
{
if (nums1[end1] > nums2[end2])
{
nums1[end--] = nums1[end1--];
}
else
nums1[end--] = nums2[end2--];
}
while (end2 >=0 )
{
nums1[end--] = nums2[end2--];
}
}
分析:时间复杂度为O(m+n),空间复杂度为O(m+n),这是这道题最优的解法。
结语
每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根。
边栏推荐
- Redis常见题型
- Grid布局介绍
- MySql将一张表的数据copy到另一张表中
- Navicat报错:1045-Access denied for user [email protected](using passwordYES)
- MYSQL unique constraint
- 行测不会概念
- 简道云-灵活易用的应用搭建平台
- MySQL 8.0.28 version installation and configuration method graphic tutorial
- Mysql implements optimistic locking
- MySQL implements sorting according to custom (specified order)
猜你喜欢
MySQL 8.0.28 version installation and configuration method graphic tutorial
Google Chrome(谷歌浏览器)安装使用
Introduction and use of apifox (1).
简道云-灵活易用的应用搭建平台
PDF file conversion format
MySQL 多表关联一对多查询实现取最新一条数据
Google 安装印象笔记剪藏插件
[Digital IC hand-tear code] Verilog fixed priority arbiter | topic | principle | design | simulation
[email protected](using passwordYES)"/>
Navicat报错:1045-Access denied for user [email protected](using passwordYES)
100 latest software testing interview questions in 2022, summary of common interview questions and answers
随机推荐
MySQL如何对SQL做prepare预处理(解决IN查询SQL预处理仅能查询出一条记录的问题)
一线大厂软件测试流程(思维导图)详解
mysql安装教程【安装版】
MySQL如何创建用户
MySQL 5.7升级到8.0详细过程
MES如何做好生产过程监控,本文给出了详细解答
MySql字符串拆分实现split功能(字段分割转列、转行)
公司不重视软件测试,新来的阿里P8给我们撰写了测试用例编写规范
Matlab学习第二天
ELK日志分析系统
SQL数据表增加列
合作的小伙伴,缺乏主人翁(owner)意识,好苦恼
MySQL 灵魂 16 问,你能撑到第几问?
Matlab论文插图绘制模板第41期—气泡图(bubblechart)
12个MySQL慢查询的原因分析
PDF file conversion format
MySQL夺命10问,你能坚持到第几问?
navicat连接MySQL报错:1045 - Access denied for user ‘root‘@‘localhost‘ (using password YES)
Navicat报错:1045 -拒绝访问用户[email protected](使用passwordYES)
利用浏览器本地存储 实现记住用户名的功能