//
// Created by YUQIONG LI on 19/10/2018.
//
#include <vector>
#include <cmath>
#include <stack>
#include <iostream>
#include <queue>
using std::queue;
using std::stack;
using std::vector;
using std::log;
using std::cout;
using std::endl;
class Solution {
public:
vector<int> dedup(vector<int> array) {
// write your solution here
vector<int> res;
if (array.empty())
return res;
// requirement is inplace
int i = 0, j = 0;
// from 0 to i: to keep
// from i+1 to j: to discard
// from j+1 to the end: to explore
int prev = array[j];
while(j+1<array.size()){
if(array[j+1] == prev)
j++;
else {
prev = array[j+1];
i++;
j++;
int temp = std::move(array[j]);
array[j] = std::move(array[i]);
array[i] = std::move(temp);
}
}
// now discard everything from i+1 to the end
array.erase(array.begin()+i+1, array.end());
return array;
}
};
int main(){
vector<int> a = {1, 2, 2, 3, 3, 3};
Solution s;
vector<int> res = s.dedup(a);
for (auto r : res)
cout << r << endl;
return 0;
}
- The trick is to do it in-place. Think of quicksort.
- Note where to change the prev value. You can change it just after the while loop, but note the array will be messed up after the swapping. So it's better to keep the prev value before swapping.
- Note where to change the prev value. You can change it just after the while loop, but note the array will be messed up after the swapping. So it's better to keep the prev value before swapping.
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.