每日算法——letcode系列

问题 Remove Duplicates from Sorted Array

Difficulty:<strong>Easy</strong></br>

<p><p>Given a sorted array, remove the duplicates in place such that each element appear only <i>once</i> and return the new length.</p>
<p>Do not allocate extra space for another array, you must do this in place with constant memory.</p>
<p>For example,<br />Given input array <i>nums</i> = [1,1,2],</p>
<p>Your function should return length = <code>2</code>, with the first two elements of <i>nums</i> being <code>1</code> and <code>2</code> respectively. It doesn't matter what you leave beyond the new length.</p></p>

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

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

难度系数：<strong>容易</strong></br>

<p><p>给定一个有序的数组，删除数组的重复的元素使得每个元素只出现<i>一</i> 次，并返回数组的长度</p>
<p> 你只能在常量内存空间中操作，不能再额外分配一个数组空间</p>
<p>举例：<br />假定数组 <i>nums</i> = [1,1,2],</p>
<p>函数返回的长度应 = <code>2</code>, 数组的前 <i>两个数</i> 分别应为<code>1</code>和<code>2</code> </p></p>

思路

方案一： STL中的unique和distance
方案二： 维护一个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;
    }
};

延伸思考

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

英文版：

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

中文版：

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