距离相等的条形码

说在前面

🎈今天给大家带来的是算法练习,题目为"距离相等的条形码"。

题目描述

在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。\
请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案，此题保证存在答案。\
示例 1：

输入：barcodes = [1,1,1,2,2,2]
输出：[2,1,2,1,2,1]

示例 2：

输入：barcodes = [1,1,1,1,2,2,3,3]
输出：[1,3,1,3,2,1,2,1]

提示：

1 <= barcodes.length <= 10000
1 <= barcodes[i] <= 10000

思路分析

题目的意思很明确，就是要我们将给定的数组barcodes重新排序，得到一个没有相邻元素相等的数组。\

1.统计字频

首先我们需要先统计每个数字出现的频率

let map = {};
for(let i = 0; i < barcodes.length; i++){
    map[barcodes[i]] = (map[barcodes[i]] || 0) + 1;
}

2.词频排序

根据词频我们对key进行排序

let keys = Object.keys(map).sort((a,b)=>{
    return map[b] - map[a];
});

3.奇偶分开插入

按照词频从高到低，先将奇数位置填满，然后在将偶数位置填满，因为题目中保证此题保证存在答案，所以这样得出的数组即是正确的。

let res = new Array(barcodes.length);
let l = 0;
for(let i = 0; i < res.length; i+=2){
    res[i] = keys[l];
    map[keys[l]]--;
    if(map[keys[l]] == 0) l++;
}
for(let i = 1; i < res.length; i+=2){
    res[i] = keys[l];
    map[keys[l]]--;
    if(map[keys[l]] == 0) l++;
}

AC代码

/**
 * @param {number[]} barcodes
 * @return {number[]}
 */
var rearrangeBarcodes = function(barcodes) {
    if(barcodes.length < 3) return barcodes;
    let map = {};
    for(let i = 0; i < barcodes.length; i++){
        map[barcodes[i]] = (map[barcodes[i]] || 0) + 1;
    }
    let keys = Object.keys(map).sort((a,b)=>{
        return map[b] - map[a];
    });
    let res = new Array(barcodes.length);
    let l = 0;
    for(let i = 0; i < res.length; i+=2){
        res[i] = keys[l];
        map[keys[l]]--;
        if(map[keys[l]] == 0) l++;
    }
    for(let i = 1; i < res.length; i+=2){
        res[i] = keys[l];
        map[keys[l]]--;
        if(map[keys[l]] == 0) l++;
    }
    return res;
};

说在后面

🎉这里是JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。