904
技術社區[雲棲]
[LeetCode]80.Remove Duplicates from Sorted Array II
【題目】
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].
【代碼】
/*********************************
* 日期：2014-01-15
* 作者：SJF0115
* 題目: 80.Remove Duplicates from Sorted Array II
* 來源：https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
* 結果：AC
* 來源：LeetCode
* 總結：
**********************************/
#include <iostream>
#include <stdio.h>
using namespace std;
// 時間複雜度 O(n)，空間複雜度 O(1)
class Solution {
public:
//A數組的重要特點是已經排序
int removeDuplicates(int A[], int n) {
if(n == 0){
return 0;
}
else if(n == 1){
return 1;
}
//新數組下標
int index = 2;
for(int i = 2;i < n;i++){
if(A[i] != A[index-2]){
A[index++] = A[i];
}
}
return index;
}
};
int main() {
int result;
Solution solution;
int A[] = {1,1,2,2,2,2,4,4,5,6,8,8,8};
result = solution.removeDuplicates(A,13);
printf("Length:%d\n",result);
for(int i = 0;i < result;i++){
printf("%d ",A[i]);
}
return 0;
}
最後更新：2017-04-03 12:54:29