將數組與目標進行排序以儘量減少重複序列

Question

好吧，我有一個websocket客戶端連接數組。想象一下，這個數組包含連接到幾個不同的機器。想象一下，每個不同的字母（1,2,3等）代表不同的主機。這可能是這樣的：

const conns = [1,1,1,3,3,1,3,2,2,2,2,3,2,1,1,2,2]; 

我願做的事，就是有點像數組這樣：

const conns = [1,2,3,1,2,3,1,2,3, ... etc]; 

的基本原理是，如果客戶沒有迴應，我不想重試到同一個主機，我想嘗試發送消息到不同主機上的客戶端，並且以後只能回到原來的主機。這基本上像循環類型的事情。

我認爲最好的方式來排序的數組像這樣的：

1. 找到所有的不同的主機（獨特的字母）的陣列
2. 遍歷這個獨特的名單中，並拼接開來的項目原來的陣列，我走了。

這裏是JS代碼，我對上面的算法：

const list = [1,2,3,4,5,1,1,1,1,1,2,3,4,5,1,2,11,3,3,3,3,3,4,4,4,1,1,1]; 

const _ = require('lodash'); 

function findAndRemoveFirstMatch(m, list){ 
    for(var i = 0; i < list.length; i++){ 
     if(m === list[i]){ 
      return list.splice(i,1)[0]; 
     } 
    } 
} 

function getSorted(list){ 

    const ret = []; 

    const set = _.uniqBy(list, function(x){ 
     return x; 
    }); 

    while(list.length > 0){ 

     var i = 0; 
     while(i < set.length && list.length > 0){ 
      var item; 
      if(item = findAndRemoveFirstMatch(set[i],list)){ 
       ret.push(item); 
      } 
      i++; 
     } 

    } 

    return ret; 

} 

console.log(getSorted(list)); 

//給上面的輸入，我們得到：

[ 1, 2, 3, 4, 5, 11, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 3, 4, 1, 3, 4, 1, 3, 1, 3, 1, 1, 1 ] 

我不是這個代碼的驕傲，並想知道是否有更好的方法來做到這一點。上述內容適用於此輸入，但希望找到一種清理它並使其更通用的好方法。

有沒有更好/更快的方法來做到這一點？

Answer 1

你可以做不同的是：

• 排序輸入 - 這將有助於以後

• 找到相等的元素的最大數（10在你的榜樣，爲元素= 1），CNT

• 創建CNT水桶在他們

分發元素

• 投入要素的排序順序逐個放入下一個桶循環原理

• 合併桶

這樣，你到底得到更長的系列，1小於開頭。

[1, 2, 4, 1, 2, 4, 1, 2, 4, 1, 3, 4, 1, 3, 4, 1, 3, 5, 1, 3, 5, 1, 3, 11, 1, 3, 1, 3] 

不好的情況是當一個元素出現超過n/2次，但這是不可避免的。

var list = [1,2,3,4,5,1,1,1,1,1,2,3,4,5,1,2,11,3,3,3,3,3,4,4,4,1,1,1]; 
var a = list.sort(function(a, b) { return a - b; }); 
var cnt = a.reduce(function(res, cur) { 
    if (cur == res[0]) 
    return [cur, res[1]+1, Math.max(res[1]+1, res[2])] 
    else 
    return [cur, 1, Math.max(1, res[2])]; 
}, [null, 0, 0])[2]; 

var buckets = []; 
for (var i = 0; i < cnt; i++) 
    buckets[i] = []; 

var j = 0; 
for (var i = 0; i < a.length; i++) { 
    buckets[j].push(a[i]); 
    j = (j+1)%cnt; 
} 

var res = buckets.reduce(function(r, cur) { 
    return r.concat(cur); 
}); 

如果硬要從一開始鍵的完整列表，它也有可能：

var list = [1,2,3,4,5,1,1,1,1,1,2,3,4,5,1,2,11,3,3,3,3,3,4,4,4,1,1,1]; 
var a = list.sort(function(a, b) { return a - b; }); 
var cnt = a.reduce(function(res, cur) { 
    if (cur == res[0]) 
     return [cur, res[1]+1, Math.max(res[1]+1, res[2])] 
    else 
     return [cur, 1, Math.max(1, res[2])]; 
}, [null, 0, 0])[2]; 

var buckets = []; 
for (var i = 0; i < cnt; i++) 
    buckets[i] = []; 

var j = 0; 
var cur = null; 
for (var i = 0; i < a.length; i++) { 
    if (cur != a[i]) 
     j = 0; 
    buckets[j].push(a[i]); 
    j = j+1; 
} 

var res = buckets.reduce(function(r, cur) { 
    return r.concat(cur); 
});