Leetcode—— 删除排序数组中的重复项——C语言

简介: Leetcode—— 删除排序数组中的重复项——C语言

💗1.题目💗


给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。


考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:


更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。

返回 k 。

判题标准:


系统会用下面的代码来测试你的题解:


int[] nums = [...]; // 输入数组

int[] expectedNums = [...]; // 长度正确的期望答案


int k = removeDuplicates(nums); // 调用


assert k == expectedNums.length;

for (int i = 0; i < k; i++) {

   assert nums[i] == expectedNums[i];

}

如果所有断言都通过,那么您的题解将被 通过。


示例 1:


输入:nums = [1,1,2]

输出:2, nums = [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]

解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。


提示:


        1 <= nums.length <= 3 * 104

         -104 <= nums[i] <= 104

         nums 已按 非严格递增 排列


💗2.解答💗


❣️1.双指针❣️

时间复杂度为O(N),空间复杂度为O(1);

image.png

1、dst和src不相等,++dst

2、dst和src相等,++src

a[src]=a[dst]

++dst

本质是dst依次找跟src位置不相等值,依次从前往后覆盖存储


int removeDuplicates(int* nums, int numsSize) 
{
    int dst=1,src=0;
    while(dst<numsSize)
    {
        if(nums[src]!=nums[dst])
        {
         //   ++src;
          //  nums[src]=nums[dst];
           // ++dst;
            nums[++src]=nums[dst++];
        }
        else
        {
            ++dst;
        }
    }
    return src+1;//返回删除重复项后数组长度
}

image.png

❣️2. 暴力求解❣️

用i遍历数组,用j记录重复元素次数

int removeDuplicates(int* nums, int numsSize){
    int i, j = 0;                      
    for(i=0;i<numsSize-1;i++){          
        if(nums[i] == nums[i + 1])       
            j += 1;                      
        // 遇到重复的元素,j记录增加1;当for循环结束j累加完成,也代表共需要删去的数组长度
        nums[i + 1 - j] = nums[i + 1];  // 将下一个元素向前覆盖到非重复位置
    }
    numsSize -= j;                      // 删去数组冗余长度(遇到j个重复元素,所以原长度减j)
    return numsSize;
}

❣️3.比较写入❣️

时间复杂度为O(N),空间复杂度为O(1);


前后比较,遇到不相同的项,则在数组对应的位置写入即可


利用k的值代表有多少个不一样的项,前后比较,每遇到不同的项,(k+1)即为后面不同项在nums的对应下标,将后者直接读入nums中, 注意:由于每次写入的都是后面的项,最后返回时加上第一项;


int removeDuplicates(int* nums, int numsSize){
    int k= 0;
    for(int i = 0; i < numsSize-1; i++ )
    {
        if(nums[i]!=nums[i+1])
        {
            nums[++k] = nums[i+1];
        }
    }
    return k+1;
}
相关文章
|
2天前
|
C语言
C语言----数组----二分查找
C语言----数组----二分查找
|
2天前
|
C语言
C语言---单身狗(1)---在一个整型数组中,只有一个数字出现一次,其他数组都是成对出现的,请找出那个只出现一次的数字
C语言---单身狗(1)---在一个整型数组中,只有一个数字出现一次,其他数组都是成对出现的,请找出那个只出现一次的数字
|
2天前
|
C语言
C语言----关于二维数组传参的本质相关的知识点(数组指针、指针数组)
C语言----关于二维数组传参的本质相关的知识点(数组指针、指针数组)
|
2天前
|
C语言
C语言---数组中逆序输出--新
C语言---数组中逆序输出--新
|
2天前
|
C语言
C语言--指针数组和数组指针的区别
C语言--指针数组和数组指针的区别
|
2天前
|
C语言
C语言-----将数组A中的内容和数组B中的内容进行交换。(数组一样大)
C语言-----将数组A中的内容和数组B中的内容进行交换。(数组一样大)
|
2天前
|
C语言
C语言---函数--数组---创建一个整形数组,完成对数组的3种操作
C语言---函数--数组---创建一个整形数组,完成对数组的3种操作
|
2天前
|
C语言
C语言----将数组A中的内容和数组B中的内容进行交换。(数组一样大)
C语言----将数组A中的内容和数组B中的内容进行交换。(数组一样大)
|
2天前
|
C语言
C语言--数组合并
C语言--数组合并
|
2天前
|
存储 C语言