脚本宝典收集整理的这篇文章主要介绍了

Remove Duplicates from Sorted Array

脚本宝典小编觉得挺不错的,现在分享给大家,也给大家做个参考,希望能帮助你少写一行代码,多一份安全和惬意。

每日算法——letcode系列

问题 Remove Duplicates from Sorted Array

Difficulty:Easy

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

// C++
class Solution {
public:
   int removeDuplicates(vector<int>& nums) {
       
   }
};

翻译 移除有序数组中重复元素

难度系数:容易

给定一个有序的数组,删除数组的重复的元素使得每个元素只出现一 次,并返回数组的长度

你只能在常量内存空间中操作,不能再额外分配一个数组空间

举例:
假定数组 nums = [1,1,2],

函数返回的长度应 = 2, 数组的前 两个数 分别应为12

思路

方案一: STL中的uniquedistance
方案二: 维护一个index记录不重复的元素

代码

方案一:

// C++
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        auto firstIterator = nums.begin();
        auto endIterator = nums.end();
        return static_cast<int>(distance(firstIterator, unique(firstIterator, endIterator)));
    }
};

方案二:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()){
            return 0;
        }
        
        int index = 0;
        for (size_t i = 1; i < nums.size(); ++i) {
            if (nums[index] != nums[i]){
                nums[++index] = nums[i];
            }
        }
        return ++index;
    }
};

延伸思考

删除让我想到一个出自《编程珠玑》的找重复的算法题

英文版:

Given a sequential file containing 4,300,000,000 32-bit intergers, how can you find one that appears at least twice?

中文版:

给定包含4 300 000 000 个 32 位整数的顺序文件, 如何找出一个出现至少两次的整数?

总结

以上是脚本宝典为你收集整理的

Remove Duplicates from Sorted Array

全部内容,希望文章能够帮你解决

Remove Duplicates from Sorted Array

所遇到的程序开发问题,欢迎加入QQ群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过