C++实现LeetCode(26.有序数组中去除重复项)

[LeetCode] 26. Remove Duplicates from Sorted Array 有序数组中去除重复项

Given a sorted array nums, 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 by modifying the input array in-place with O(1) extra memory.

Example 1:

Given 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 returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length =

5

, with the first five elements of

nums

being modified to 

0

,

1

,

2

,

3

, and 

4

respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}

这道题要我们从有序数组中去除重复项，和之前那道 Remove Duplicates from Sorted List 的题很类似，但是要简单一些，因为毕竟数组的值可以通过下标直接访问，而链表不行。那么这道题的解题思路是使用快慢指针来记录遍历的坐标，最开始时两个指针都指向第一个数字，如果两个指针指的数字相同，则快指针向前走一步，如果不同，则两个指针都向前走一步，这样当快指针走完整个数组后，慢指针当前的坐标加1就是数组中不同数字的个数，代码如下：

解法一：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int pre = 0, cur = 0, n = nums.size();
        while (cur < n) {
            if (nums[pre] == nums[cur]) ++cur;
            else nums[++pre] = nums[cur++];
        }
        return nums.empty() ? 0 : (pre + 1);
    }
};

我们也可以用 for 循环来写，这里的j就是上面解法中的 pre，i就是 cur，所以本质上都是一样的，参见代码如下：

解法二：

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

这里也可以换一种写法，用变量i表示当前覆盖到到位置，由于不能有重复数字，则只需要用当前数字 num 跟上一个覆盖到到数字 nums[i-1] 做个比较，只要 num 大，则一定不会有重复（前提是数组必须有序），参见代码如下：

解法三：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0;
        for (int num : nums) {
            if (i < 1 || num > nums[i - 1]) {
                nums[i++] = num;
            }
        }
        return i;
    }
};

到此这篇关于C++实现LeetCode(26.有序数组中去除重复项)的文章就介绍到这了,更多相关C++实现有序数组中去除重复项内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(20.验证括号)

    [LeetCode] 20. Valid Parentheses 验证括号 Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open

  • C++实现LeetCode(88.混合插入有序数组)

    [LeetCode] 88. Merge Sorted Array 混合插入有序数组 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1and nums2 are m and n respectively. You may assume that nums1 has

  • C++实现LeetCode(19.移除链表倒数第N个节点)

    C++实现LeetCode(19.移除链表倒数第N个节点)

    [LeetCode] 19. Remove Nth Node From End of List 移除链表倒数第N个节点 Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the en

  • C++实现LeetCode(21.混合插入有序链表)

    [LeetCode] 21. Merge Two Sorted Lists 混合插入有序链表 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2

  • C++实现LeetCode(18.四数之和)

    [LeetCode] 18. 4Sum 四数之和 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: Elements in a quadruplet (a,b,c,d) must be

  • C++实现LeetCode(83.移除有序链表中的重复项)

    [LeetCode] 83. Remove Duplicates from Sorted List 移除有序链表中的重复项 Given a sorted linked list, delete all duplicates such that each element appear only once. Example 1: Input: 1->1->2 Output: 1->2 Example 2: Input: 1->1->2->3->3 Output: 1-

  • C++实现LeetCode(17.电话号码的字母组合)

    [LeetCode] 17. Letter Combinations of a Phone Number 电话号码的字母组合 Given a string containing digits from 2-9inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone butt

  • C++实现LeetCode(26.有序数组中去除重复项)

    [LeetCode] 26. Remove Duplicates from Sorted Array 有序数组中去除重复项 Given a sorted array nums, 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

  • C++实现LeetCode(80.有序数组中去除重复项之二)

    [LeetCode] 80. Remove Duplicates from Sorted Array II 有序数组中去除重复项之二 Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array, you mus

  • java算法入门之有效的括号删除有序数组中的重复项实现strStr

    java算法入门之有效的括号删除有序数组中的重复项实现strStr

    目录 1.LeetCode 20.有效的括号 题目 小编菜解 思路及算法 大神解法 2.LeetCode 26.删除有序数组中的重复项 题目 小编菜解初版 小编菜解改进版 思路及算法 大神解法 3.LeetCode 28.实现strStr 题目 小编菜解 大神解法 也许,我们永远都不会知道自己能走到何方,遇见何人,最后会变成什么样的人,但一定要记住,能让自己登高的,永远不是别人的肩膀,而是挑灯夜战的自己,人生的道路刚刚启程,当你累了倦了也不要迷茫,回头看一看,你早已不再是那个年少轻狂的少年. 1

  • C语言 详解如何删除有序数组中的重复项

    C语言 详解如何删除有序数组中的重复项

    目录 删除有序数组中的重复项Ⅰ a.思路 b.图解 c.代码 d.思考 删除有序数组中的重复项Ⅱ a.思路 b.图解 c.代码 d.思考 删除有序数组中的重复项Ⅰ a.思路 定义变量 int dest=0,cur=1,nums[cur]与nums[dest]逐一比较. nums[cur]!=nums[dest],将nums[cur]放入dest下一个位置,更新dest. nums[cur]!=nums[dest],cur移动. cur==numsSize,结束.返回dest+1. b.图解 c.

  • JavaScript删除有序数组中的重复项

    JavaScript删除有序数组中的重复项

    目录 如果有一个有序数组 nums ,要求原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度. 不要使用额外的数组空间,必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成. 说明: 为什么返回数值是整数,但输出的答案是数组呢? 注意:输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的. 你可以想象内部操作如下: // nums 是以"引用"方式传递的.也就是说,不对实参做任何拷贝 int len = removeDu

  • js数组中去除重复值的几种方法

    在日常开发中,我们可能会遇到将一个数组中里面的重复值去除,那么,我就将我自己所学习到的几种方法分享出来 去除数组重复值方法: 1,利用indexOf()方法去除 思路:创建一个新数组,然后循环要去重的数组,然后用新数组去找要去重数组的值,如果找不到则使用.push添加到新数组,最后把新数组返回回去就行了 看不懂没关系,上代码就比较容易懂了 function fun(arr){ let newsArr = []; for (let i = 0; i < arr.length; i++) { if(

  • C++实现LeetCode(82.移除有序链表中的重复项之二)

    [LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项之二 Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Example 1: Input: 1->2->3->3->4->4->5 Outp

  • PHP二维数组实现去除重复项的方法【保留各个键值】

    本文实例讲述了PHP二维数组实现去除重复项的方法.分享给大家供大家参考,具体如下: 对于如下二维数组,要求对其进行去重: $arr = array( '0'=>array( 'name'=>'james', 'age'=>30, ), '1'=>array( 'name'=>'susu', 'age'=>26, ), '2'=>array( 'name'=>'james', 'age'=>30, ), 'new'=>array( 'name'=&

  • JS实现合并两个数组并去除重复项只留一个的方法

    本文实例讲述了JS实现合并两个数组并去除重复项只留一个的方法.分享给大家供大家参考,具体如下: //It's merge arr1 and arr2 , delete the same element only leave one //It's only apdapter array. If object, no. //The sequence of the two array is not required. mergeArray:function (arr1, arr2){ for (var

随机推荐