LeetCode-26-已排序数组去重
问题描述
LeetCode – Remove Duplicates from Sorted Array
对已经排好序的数组,去除其中重复的元素,并返回去重后的长度如[1,2,2,3,3],去重后为[1,2,3] ,去重后长度为3
算法1
两个指针,前者(p)记录当前去重后的最后一个元素,后者(i)不断遍历数组,寻找新元素。
int removeDuplicates(int* nums, int numsSize){ if(numsSize == 0) return 0; int p = 0; // 指向当前去重后数组的最后一个元素,初始为0位置 for(int i = 1; i < numsSize; i++){ // 发现新的元素,放到p+1位置 if( nums[i] != nums[p]) { p ++; nums[p] = nums[i]; } } return p + 1; }
算法2
来自Discuss区
遍历数组,使用count记录当前出现了多少次重复
如果出现重复,则count++
如果没有重复,则把当前的元素 i 放到它在去重后数组的位置 i-count处
int count = 0; for(int i = 1; i < n; i++){ if(A[i] == A[i-1]) count++; else A[i-count] = A[i]; } return n-count;
作者:JarvisChu
原文链接:LeetCode-26-已排序数组去重
版权声明:自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0