Deduplication2 (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 // counter : how many prev elements you have seen int prev = array[j]; int counter = 1; // at most two consecutive numbers while(j+1<array.size()){ if(array[j+1] == prev && counter == 2) { counter++; j++; } else if (array[j+1] == prev && counter == 1){ i++; j++; int temp = std::move(array[j]); array[j] = std::move(array[i]); array[i] = std::move(temp); counter++; } else { prev = array[j+1]; counter = 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,2,3,3,3}; Solution s; vector<int> res = s.dedup(a); for (auto r : res) cout << r << endl; return 0; }
Note the use of counter. In case 2: same element but still not reached max counter, we need to swap elements too.

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.