【Remove Duplicates from Sorted Array II】cpp
题目:
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3]
,
Your function should return length = 5
, and A is now [1,1,2,2,3]
.
代码:
class Solution {
public:
int removeDuplicates(int A[], int n) {
if (n <= ) return n;
int index = ;
for (int i= ; i<n; i++)
{
if ( A[index-]!=A[i] )
{
A[index++] = A[i];
}
}
return index;
}
};
Tips:
1. index始终指向下一个要插入元素的位置
2. 判断当前元素与index-2位置元素是否相等,如果不等就可以插入,保证没有连续三个相同的元素
3. 这里用到些数学归纳法的技巧:
a. 只要保证第1-第3个元素不是都相同的
b. 并且再后面每一步添加元素的时候判断都不是相同的
则可得结论一直到条件结束,调整后的数组中不会有三个连续重复的元素
========================================
第二次过这道题卡住了一下,复习了第一次写的程式,改出了AC的代码。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if ( nums.size()< ) return nums.size();
int prev = ;
for ( int i=; i<nums.size(); ++i )
{
if ( nums[prev-]!=nums[i] )
{
nums[prev++] = nums[i];
}
}
return prev;
}
};
tips:
这种数学归纳法之类的去重代码,可以总结出一定的规律
第一个指针 prev = 可以保持的重复数量 (这个指针指示当前可插入的位置)
第二个指针 i 从 可以保持重复数量下标开始 一直到数组长度最后
去重条件判断nums[prev-可以保持重复的数量]!=nums[i]
这样就可以获得满足题意的程式。
================================
这里还有一种特殊的case,如果出现重复的就不要了呢?写出了下面的程式
// special case
class SolutionS{
public:
static int removeDuplicates(vector<int>& nums)
{
if ( nums.size()< ) return nums.size();
int i=;
int prev = nums[]!=nums[] ? : ;
while (i<nums.size()-)
{
if (nums[i]!=nums[i-] && nums[i]!=nums[i+])
{
nums[prev++]=nums[i];
}
i++;
}
if ( nums[i]!=nums[i-] ) nums[prev++]=nums[i];
return prev;
}
};
这个程式是自己写的,自测了一些case。
思路很朴素:
1. 维护一个prev作为待插入的位置
2. 判断一个元素与前后元素是否相等
3. 处理第一个和末尾元素(第一个没有前驱,末尾没有后继,所以要特殊处理)
====================================================
还有一种情况,如果数组不是排序的,就用hashtable记录每个数字出现的次数。
最新文章
- SQL Server存储过程多角度介绍
- js获取网络图片的宽和高
- javaweb学习总结十七(web应用组织结构、web.xml作用以及配置虚拟主机搭建网站)
- windows 7 下安装 IIS 和 ArcGis Server 9.3 遇到的问题及解决方法
- XmlHttp对象
- 对拍 For Linux
- linux下一个Oracle11g RAC建立(八)
- 763A - Timofey and a tree
- 不想再被鄙视?那就看进来! 一文搞懂Python2字符编码
- Linux常用命令之文件处理命令
- 设计模式之代理模式(Proxy)(2)
- [物理学与PDEs]第5章习题1 矩阵的极分解
- String 、Stringbuilder和StringBuffer的区别
- Unity RigidBodyFPSController 鼠标不显示
- jdk下载及环境变量配置
- BZOJ1396 识别子串 字符串 SAM 线段树
- [easyUI] autocomplete 简单自动完成以及ajax从服务器端完成
- nginx FastCGI错误Primary script unknown解决办法
- iOS开发-带Placeholder的UITextView实现
- [SQL Server 2014] SQL Server 2014新特性探秘