- 题目
- 思路1--暴力遍历
- 思路2--开辟额外空间
- 思路3--双指针
题目链接: 26. 删除有序数组中的重复项
思路1–暴力遍历
思路:
由于是有序的,那么就可以遍历数组,找相邻两个数是否相等;
如果相等那么就把数组后面的元素往前移动;同时numsSize–;
注意:由于遍历数组时候,后面元素往前移动了,所以遍历的元素下标i–;
时间复杂度O(n)
代码实现:
int removeDuplicates(int* nums, int numsSize) { //控制号结束条件即可!! for(int i = 0;i
思路2–开辟额外空间开辟额外空间temp,用来保存只出现过一次的数字,就像相当于移除了重复元素;
时间复杂度O(n);
空间复杂度度O(n);
实现代码:
int removeDuplicates(int* nums, int numsSize) { //假如数组没有元素,直接返回0 if(numsSize == 0) return 0; int* temp = (int*)malloc(sizeof(int)*numsSize); //先给零时数组一个值 temp[0] = nums[0]; int cur = 0; //指向零时数组的下标 //从nums[1]开始与临时数组的元素比较,不相同的直接放进去temp for(int i = 1;i
思路3–双指针用src = 1;dst = 0; 指向nums数组下标;
只要nums[src] != nums[dst] ;那么就把 src对应的值赋值给dst+1的位置;同时src++;
只要nums[src] 等于 nums[dst],那么就移动src++;
时间复杂度O(n);
空间复杂度O(1);
int removeDuplicates(int* nums, int numsSize) { if(numsSize==0) return 0; int src = 1; //用来移动的指针 int dst = 0; //用来存放不同值的指针 while(src < numsSize){ //如果不相等那么就赋值过去 if(nums[src] != nums[dst]){ nums[++dst] = nums[src++]; }else //相等就移动src { src++; } } return dst+1; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)