Deduplication1 (inplace)

// // 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.

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.