首页 > 其他 > 详细

26. Remove Duplicates from Sorted Array

时间:2021-04-07 15:35:24      阅读:24      评论:0      收藏:0      [点我收藏+]

问题:

去除有序数组中重复的数字。

Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: 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:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation: 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.
 

Constraints:
0 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums is sorted in ascending order.

  

解法:slow-fast pointers(快慢指针法)

  • 0~low:代表不重复的数组。
  • fast:去检测重复的元素,若找到一个不重复的数,
    • swap(low+1, fast)
    • low++

不重复的元素 fast 交换至 前面第一个不符合要求的位置 low+1

继续探测下一个元素 fast++

 

代码参考:

 1 class Solution {
 2 public:
 3     int removeDuplicates(vector<int>& nums) {
 4         int i=0, j=1;
 5         int n=nums.size();
 6         if(n==0) return 0;
 7         while(j<n) {
 8             if(nums[i]!=nums[j]) {
 9                 i++;
10                 swap(nums[i], nums[j]);
11             }
12             j++;
13         }
14         return i+1;
15     }
16 };

 

26. Remove Duplicates from Sorted Array

原文:https://www.cnblogs.com/habibah-chang/p/14627388.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!