In a warehouse, there is a row of barcodes, where the i
-th barcode is barcodes[i]
.
Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.
Example 1:
Input: [1,1,1,2,2,2] Output: [2,1,2,1,2,1]
Example 2:
Input: [1,1,1,1,2,2,3,3] Output: [1,3,1,3,2,1,2,1]
Note:
1 <= barcodes.length <= 10000
1 <= barcodes[i] <= 10000
Soluton: Sorting
Sort the element by their frequency in descending order. Fill the most frequent element first in even positions, if reach the end of the array, start from position 1 then 3, 5, …
Time complexity: O(nlogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua, 216 ms, 18.2 MB class Solution { public: vector<int> rearrangeBarcodes(vector<int>& barcodes) { const int n = barcodes.size(); vector<int> f(10001); for (int v : barcodes) ++f[v]; sort(begin(barcodes), end(barcodes), [&](const int a, const int b){ return f[a] == f[b] ? a > b : f[a] > f[b]; }); vector<int> ans(n); int pos = 0; for (int v : barcodes) { ans[pos] = v; if ((pos += 2) >= n) pos = 1; } return ans; } }; |
Solution 2: Find the most frequent
Actually, we only need to find the most frequent element and put in the even positions, then put the rest of the groups of elements in any order.
e.g. [1, 1, 2, 2, 2, 2, 2, 3, 4]
Can be
5*2 [2 – 2 – 2 – 2 – 2]
4*1 [2 4 2 – 2 – 2 – 2]
3*1 [2 4 2 3 2 – 2 – 2]
1*2 [ 2 3 2 3 2 1 2 1 2]
if we start with any other groups rather than 2, if will become:
[3 2 2 – 2 – 2 – 2 ] which is wrong…
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua, 172 ms (99.89%), 18 MB (< 100%) class Solution { public: vector<int> rearrangeBarcodes(vector<int>& barcodes) { constexpr int kMaxV = 10001; const int n = barcodes.size(); vector<int> f(kMaxV); int max_f = 0; int max_v = 0; for (int v : barcodes) if (++f[v] > max_f) { max_f = f[v]; max_v = v; } vector<int> ans(n); int pos = 0; while (f[max_v]-- > 0) { ans[pos] = max_v; if ((pos += 2)>= n) pos = 1; } for (int v = 1; v < kMaxV; ++v) { while (f[v]-- > 0) { ans[pos] = v; if ((pos += 2) >= n) pos = 1; } } return ans; } }; |