关于看我是怎么C的你叫出来了的知识点,濮阳头条网将为你整理了下面这些知识。
作为一个程序员,看到一些神奇的编程题目总是让我无法抵挡,今天就来分享一下如何看出“我是怎么C的你叫出来了”这道神奇的去重算法。
背景介绍
“我是怎么C的你叫出来了”是一道常见的去重算法题目,其思路为在O(n)的时间复杂度内去除一个数组中的重复元素,并将不重复的元素存放在数组前面,返回不重复元素的个数。
核心思路
该题的核心思路为双指针法,定义两个指针i,j初始化都指向数组的第一个元素,当发现nums[j]与nums[i]不同时,将num[j]的值赋给nums[i+1],然后i指针向后移一位,将j指针再向后移,继续比较,如此往复直至j遍历完整个数组。
步骤解析
1. 定义两个指针i,j,初始化都指向数组的第一个元素。
int i = 0, j = 0;
2. 当发现nums[j]与nums[i]不同时,将nums[j]的值赋给nums[i+1],然后i指针向后移一位。
if(nums[i] != nums[j]){
i++;
nums[i] = nums[j];
}
3. 将j指针向后移,继续比较,如此往复直至j遍历完整个数组。
j++;
代码实现
int removeDuplicates(vector<int>& nums) {
if(nums.empty()) return 0;
int i = 0, j = 0;
while(j < nums.size()){
if(nums[i] != nums[j]){
i++;
nums[i] = nums[j];
}
j++;
}
return i+1;
}
总结
通过本篇文章,读者可以了解到如何看出“我是怎么C的你叫出来了”这道神奇的去重算法。该题核心思路为双指针法,定义两个指针i,j,当发现nums[j]与nums[i]不同时,将nums[j]的值赋给nums[i+1],然后i指针向后移一位,将j指针再向后移,继续比较,如此往复直至j遍历完整个数组。通过该题的解析,不仅可以提高我们的编程能力,还可以加深对双指针法这种算法思想的理解。
参考文献:
- 题目来源:力扣(LeetCode)
- 原题链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
- 作者:Nancy
- 本文链接:https://www.zhihu.com/people/zingbot-51/posts