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 <= 100001 <= barcodes[i] <= 10000题目大意：
给出一个数组，要求返回数组中的数字乡邻之间不相等。
解题思路：
统计每个数字出现的次数
起初思路，奇偶交错排列，先排偶数位置，再排奇数位置，但是会出现 1 2 2 3 得到 1 2 2 3 这样的结果
发现会出现某一个数出现的次数大于等于当前个数的一般，但是这种情况只有一个，所以我们需要先在偶数位置上排这个数，然后再排列其他数。
class Solution { public: vector<int> rearrangeBarcodes(vector<int>& b) { int nums[10000+100]; int state = -1; int max_num=0; memset(nums,0,sizeof(nums)); for(int i=0;i<b.size();i++){ nums[b[i]]++; max_num = max(max_num, nums[b[i]]); if(max_num>=int(b.size()/2) && max_num == nums[b[i]]){ state = b[i]; } } int ou_start = 0; int ji_start = 1; vector<int> ans(b.size(), 0); if(state!=-1){ while(nums[state]){ ans[ou_start] = state; ou_start += 2; nums[state]--; } } for(int i=1;i<=10000;i++){ if(nums[i]){ while(nums[i]){ if(ou_start<b.size()){ ans[ou_start] = i; ou_start += 2; }else{ ans[ji_start] =i; ji_start += 2; } nums[i]--; } } } return ans; } };
