【Leetcode】1054. Distant Barcodes（138周赛第四题）（排列）

Bertha 。 2022-01-27 11:15 183阅读 0赞

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.  `1 <= barcodes.length <= 10000`
2.  `1 <= 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;
            
        }
            
    };