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;
}
相关文章
|
1天前
|
C++ Python
二刷力扣--数组
二刷力扣--数组
TU^
|
2天前
|
存储 编译器 程序员
C语言之数组
C语言之数组
TU^
9 1
|
2天前
|
存储 程序员 编译器
【C语言基础】:数组
【C语言基础】:数组
|
3天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
3天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
3天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
1天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
3天前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
3天前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)