天天看点

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

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

题目:

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

解法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;

}

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