26. 删除有序数组中的重复项(三种思路：C实现)

26. 删除有序数组中的重复项(三种思路：C实现) 题目

文章目录

• 题目
• 思路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;
}
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/4652720.html