行列词典式排序

我有长度含有长度3.我想建立一个数组B串n阵列A其中A每个串通过其秩替换A相对于所述词典排序。（注意：A可以有重复，所以B也可以有重复）。行列词典式排序

假设的JavaScript A.sort()执行时间O(n)基数排序的A，我怎么能建立O(n)时间B从A？

例子：如果A是

['abb', 'ada', 'bba', 'bba', 'dab', 'bad']

然后B是

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

（注：你可以假设数组赋值需要一定的时间。）

来源

2013-05-15 Randomblue

'sort'是用JavaScript中的基数排序实现的吗？如果这很有趣，你有一些参考？ –

'A'可以重复吗？如果是这样，会发生什么？ –

请注意，您不能保证在JS中使用'Array＃sort（）'的'O（n）'。我们无法控制特定env使用的排序算法。 – James

这里的跑得最快的家伙我能想到...

function cheese(a){ 
    var b = []; 
    var c = {};//hash references to make lookups really fast 
    var d = [];//desired output 
    for(var i = 0; i < a.length; i++) 
    { 
     if(!c[a[i]]) 
      b.push(a[i]); 
     c[a[i]] = true; 
    } 
    b.sort(); 
    for(i = 0; i < b.length; i++) 
    { 
     c[b[i]] = i; 
    } 
    for(i = 0; i < a.length; i++) 
     d.push(c[a[i]] + 1); 
    return d; 
}

来源

2013-05-15 22:00:33 Reimius

是不是因为forEach的使用会为每次迭代创建一个函数范围？ – Reimius

[我的重写]（http://jsfiddle.net/hN5Cy/）。 – Randomblue

我会尽力，但我不觉得很自信：跨浏览器的实现

我的解决方案可以简化

排序算法的一致性，并且它不是广泛的测试。

无论如何，这似乎给了期望的结果让我们去：

Array.prototype.getLexicoGraphic = function() { 
    var result = [], 
     sorted = this.slice(0).sort(); 

    for(var i = 0; i < sorted.length; i ++) { 
     result[i] = sorted.indexOf(this[i]) - (i - sorted.indexOf(sorted[i])) + 1;  
    } 

    return result; 
}

来源

2013-05-15 22:52:30 sixFingers

忘记了，这是小提琴：http://jsfiddle.net/dMD7p/ – sixFingers

'indexOf'运行在'O（n）'中，所以你的算法运行在'O（n^2）'中。 – Randomblue

是的。答案并不容易:) – sixFingers

构造辅助阵列，这将沿着包含值，其原有的指数 - O(n)。

[[0, 'abb'], [1, 'ada'], [2, 'bba'], [3, 'bba'], [4, 'dab'], [5, 'bad']] // Stored as 'foo' in the following examples

排序使用comparator function新创建的数组 - 根据你的假设O(n)（但我怀疑）。

foo.sort(function (a, b) { return a[1].localeCompare(b[1]); });

遍历已排序的数组并在路上创建排序数组 - O(n)。

var last = null, rank = 0, result = [], i; 
for (i = 0; i < foo.length; i++) { 
    result[foo[i][0]] = (last === null || last.localeCompare(foo[i][1]) != 0) ? ++rank : rank; 
    last = foo[i][1]; 
}

请享受您的result。

更新另一种方式如何做到这一点是通过关联数组的索引：

{ 'abb': [0], 'ada': [1], 'bba': [2, 3], 'dab': [4], 'bad': [5] }

然后您可以创建密钥（因此唯一值）的阵列，排序，并构建一个基于你的排名在那。

来源

2013-05-16 01:57:14

您的第一个解决方案不起作用。作为结果，我得到了[1,2,3,4，4,5]。 – Randomblue

我只是在构造结果数组时使用了坏的变量。现在它的固定和工作。 –

var A = ['abb', 'ada', 'bba', 'bba', 'dab', 'bad']; 
var B = []; 

// Assuming slice(0) is O(n) 
var Ap = A.slice(0); 
var H = []; 

var N = A.length; 
var i, index; 

// O(n) 
A.sort(); 

// O(n) 
for (index = 1, i = 0; i < N; i++) { 
    // Assuming that H[A[i]] is O(1) 
    if (!H[A[i]]) { 
     H[A[i]] = index; 
     index++; 
    } 
} 

// O(n) 
for (i = 0; i < N; i++) { 
    B[i] = H[Ap[i]]; 
} 
console.log(B); 

// 4 * O(n) === O(n)

来源

2013-05-16 15:30:40 higuaro

可以创建序的在O（n）的时间的阵列

var a = ...; 

var ranks = []; 
for (var i = 0; i < a.length; ++i) { ranks[i] = i; }

然后，可以定义由索引字符串比较

function cmp(i, j) { 
    return a[i] < a[j] ? -1 : a[i] = a[j] ? 0 : 1; 
}

每个比较比较整数的比较器由于字符串长度恒定，所以需要一段时间。

然后执行您的自定义排序ranks而不是使用cmp您规定的线性时间。这将产生b。

如果您需要a的排序版本，您可以在线性时间内从a和ranks重建它。

var aSorted = []; 
for (var i = 0; i < a.length; ++i) { 
    aSorted[i] = a[ranks[i]]; 
}

来源

2013-05-16 17:08:11

行列词典式排序

回答

相关问题