{"id":5218,"date":"2019-05-28T21:42:23","date_gmt":"2019-05-29T04:42:23","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5218"},"modified":"2019-05-28T22:03:20","modified_gmt":"2019-05-29T05:03:20","slug":"1054-distant-barcodes","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/1054-distant-barcodes\/","title":{"rendered":"\u82b1\u82b1\u9171 1054. Distant Barcodes"},"content":{"rendered":"\n<p>In a warehouse, there is a row of barcodes, where the&nbsp;<code>i<\/code>-th barcode is&nbsp;<code>barcodes[i]<\/code>.<\/p>\n\n\n\n<p>Rearrange the barcodes so that no two adjacent barcodes are equal.&nbsp; You may return any answer, and it is guaranteed an answer exists.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted; crayon:false\"><strong>Input: <\/strong>[1,1,1,2,2,2]\n<strong>Output: <\/strong>[2,1,2,1,2,1]\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted; crayon:false\"><strong>Input: <\/strong>[1,1,1,1,2,2,3,3]\n<strong>Output: <\/strong>[1,3,1,3,2,1,2,1]<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><code>1 &lt;= barcodes.length &lt;= 10000<\/code><\/li><li><code>1 &lt;= barcodes[i] &lt;= 10000<\/code><\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Soluton: Sorting<\/strong><\/h2>\n\n\n\n<p>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, &#8230;<\/p>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, 216 ms, 18.2 MB\nclass Solution {\npublic:\n  vector<int> rearrangeBarcodes(vector<int>& barcodes) {\n    const int n = barcodes.size();\n    vector<int> f(10001);\n    for (int v : barcodes) ++f[v];\n    sort(begin(barcodes), end(barcodes), [&](const int a, const int b){\n      return f[a] == f[b] ? a > b : f[a] > f[b];\n    });\n    vector<int> ans(n);\n    int pos = 0;\n    for (int v : barcodes) {\n      ans[pos] = v;\n      if ((pos += 2) >= n) pos = 1;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Find the most frequent<\/strong><\/h2>\n\n\n\n<p>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.<\/p>\n\n\n\n<p>e.g. [1, 1, 2, 2, 2, 2, 2, 3, 4]<br>Can be <br>5*2 [2 &#8211; 2 &#8211; 2 &#8211; 2 &#8211; 2]<br>4*1 [2 4 2 &#8211; 2 &#8211; 2 &#8211; 2]<br>3*1 [2 4 2 3 2 &#8211; 2 &#8211; 2]<br>1*2 [ 2 3 2 3 2 1 2 1 2] <\/p>\n\n\n\n<p>if we start with any other groups rather than 2, if will become:<br>[3 2 2 &#8211; 2 &#8211; 2 &#8211; 2 ] which is wrong&#8230;<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, 172 ms (99.89%), 18 MB (< 100%)\nclass Solution {\npublic:\n  vector<int> rearrangeBarcodes(vector<int>& barcodes) {\n    constexpr int kMaxV = 10001;\n    const int n = barcodes.size();\n    vector<int> f(kMaxV);\n    int max_f = 0;\n    int max_v = 0;\n    for (int v : barcodes)\n      if (++f[v] > max_f) {\n        max_f = f[v];\n        max_v = v;\n      }    \n    vector<int> ans(n);\n    int pos = 0;\n    while (f[max_v]-- > 0) {      \n      ans[pos] = max_v;\n      if ((pos += 2)>= n) pos = 1;\n    }\n    for (int v = 1; v < kMaxV; ++v) {\n      while (f[v]-- > 0) {        \n        ans[pos] = v;\n        if ((pos += 2) >= n) pos = 1;\n      }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>In a warehouse, there is a row of barcodes, where the&nbsp;i-th barcode is&nbsp;barcodes[i]. Rearrange the barcodes so that no two adjacent barcodes are equal.&nbsp; You&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[20,177,15],"class_list":["post-5218","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-medium","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5218","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5218"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5218\/revisions"}],"predecessor-version":[{"id":5222,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5218\/revisions\/5222"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5218"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5218"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5218"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}