Huge Lemon的博客

删除排序数组中的重复项与移除元素

2020-01-24

LeetCode 26. Remove Duplicates from Sorted Array & 27. remove elements

删除排序数组中的重复项

题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用$O(1)$额外空间的条件下完成。

示例 1:

给定数组 nums = [1,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。

你不需要考虑数组中超出新长度后面的元素。

算法思路

“拷贝覆盖”

如上图所示，用count来记录元素应该覆盖的步长：
在i位置时，

  • 若nums[i] == nums[i + 1]，则count++
  • 否则，countinue
    此处用了arr[]来记录每个元素应该移动的步长
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int removeDuplicates(int* nums, int numsSize) {
    int count = 0, i;
    if(numsSize == 0){  //空数组直接返回0
        return 0;
    }
    int arr[numsSize];
    arr[0]=0;
    for(i = 1; i < numsSize; i++) {
        if(nums[i - 1] == nums[i]) {
             count++;
        }
        arr[i]=count;
    }
    for(i=0; i < numsSize; i++){
         nums[i - arr[i]] = nums[i];
    }
    return numsSize - count;
}

移除元素

题目描述

给定一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用$O(1)$额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

算法思路

同样是“拷贝覆盖”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int removeElement(int* nums, int numsSize, int val){
    int count = 0, i;
    if(numsSize == 0){
        return 0;    //空数组直接返回0
    }
    for(i = 0; i < numsSize; i++){
        if(nums[i] == val){
            count++;
        } else {
            nums[i - count] = nums[i];
        }
    }
    return numsSize - count;
}

Tags: 算法 LeetCode
← C语言一些要点总结 复试笔试C语言重要简答题 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏