3

A長さ 3 の文字列を含む長さの配列があります。辞書式順序に関して、各文字列がそのランクに置き換えられるn配列を構築したいと考えています。（重複する可能性があるため、重複する可能性があることに注意してください。）BAAAB

JavaScript が時間内にA.sort()基数ソートを実行すると仮定すると、A時間内O(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

試してみますが、次の点についてあまり自信がありません。

  • ブラウザの実装全体でのソート アルゴリズムの一貫性
  • 私のソリューションは単純化される可能性があり、広範囲にテストされていません。

とにかく、望ましい結果が得られるようですので、行きましょう：

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 に答える