3

我有一个长度数组A，n其中包含长度为 3 的字符串。我想构建一个数组B，其中的每个字符串A都被其在A字典顺序方面的排名替换。（注意A可以有重复，所以B也可以有重复。）

假设 JavaScript在时间A.sort()上执行基数排序，我怎样才能及时构建？AO(n)BO(n)A

示例：如果A是

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

然后B是

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

（注意：您可以假设数组分配需要恒定的时间。）

4

5 回答 5

2

这是我能想到的最快的事情......

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-15T22:00:33.530 回答
0

您可以在 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您可以从线性时间重构它。aranks

var aSorted = [];
for (var i = 0; i < a.length; ++i) {
  aSorted[i] = a[ranks[i]];
}
于 2013-05-16T17:08:11.117 回答
0

构造辅助数组，该数组将包含该值及其原始索引 - O(n)。

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

使用比较器函数对新创建的数组进行排序- 根据您的假设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-16T01:57:14.197 回答
0 
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-16T15:30:40.883 回答
0

我会尝试，但我对以下方面不是很有信心：

  • 跨浏览器实现的排序算法一致性
  • 我的解决方案可以简化，并且没有经过广泛的测试。

无论如何，它似乎给出了预期的结果，所以让我们开始吧：

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-15T22:52:30.817 回答