598
技術社區[雲棲]
[LeetCode]26.Remove Duplicates from Sorted Array
Given a sorted array, 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 in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2,
and A is now [1,2].
【解析】
每次和已經記錄的最後一個數組元素比較，如果重複就跳過，否則將其加入數組末尾。
【代碼】
/*********************************
* 日期：2014-01-14
* 作者：SJF0115
* 題目: 26.Remove Duplicates from Sorted Array
* 來源：https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/
* 結果：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;
}
//新數組下標
int index = 0;
for(int i = 1;i < n;i++){
if(A[i] != A[index]){
A[++index] = A[i];
}
}
return index+1;
}
};
int main() {
int result;
Solution solution;
int A[] = {1,1,2,2,2,2,4,4,5,6,8};
result = solution.removeDuplicates(A,11);
printf("Length:%d\n",result);
for(int i = 0;i < result;i++){
printf("%d ",A[i]);
}
return 0;
}
最後更新：2017-04-03 12:54:29