前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >面试题-算法:删除排序数组中的重复项

面试题-算法:删除排序数组中的重复项

作者头像
别明天就今天吧
发布2020-09-07 01:09:56
3710
发布2020-09-07 01:09:56
举报
文章被收录于专栏:别明天就今天吧

算法,有多重要大家都应该知道,如果你有过大厂面试经历,那就更懂了,今天我们来一道简单的题,通过这道题学习一个技巧。

题目:

过滤一个数组中的重复元素,时间复杂度和空间复杂度最优的方式。

解法1:

public int remove(int[] nums) {

int new = 0;

for(int i=0;i<nums.length;i++){

if(i>=1){

if(nums[i] != nums[i-1]){

nums[++new]=nums[i];

}

}

}

return new+1;

}

时间复杂度:只遍历了一次,O(1);

空间复杂度:只多引入一个int变量;

思路:我的思路是后一个元素如果不等于前一个元素,则把后一个元素放入当前数组的最新不重复位置new,相等则跳过。

解法2:

public int remove(int[] nums) {

int slow = 0;

for (int quick= 1; quick < nums.length; quick++) {

if (nums[quick] != nums[slow]) {

nums[++slow] = nums[quick];

}

}

return slow+ 1;

}

思路:其实这道题的解法是快慢指针法,通过两个快慢指针去比较元素是否相同,快指针元素和最新的慢指针比较,不同则慢指针递增索引放置快指针元素,快慢指针在很多算法里都会用到。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-08-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 别明天就今天吧 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档