4

私はこのような配列を持っています

 var randomArray = [1,2,1,1,1,1,0,2,1,2,3,10,12,54,10,12] etc..

重複する要素を削除するか、これで重複する要素を見つけることができます。しかし、配列で繰り返される要素のすべての繰り返しシーケンスをログに記録したいと思います。これが私が試したコードですが、無限ループに陥っています

  for (i = 0; i < randomLength; i++) {
    var cycle = [i],
    flag = 0,
    start = i;
    for (var j = i + 1; j < randomLength; j++) {
       if (randomArray[i] == randomArray[j]) {
         cycle.push(randomArray[j]);
         while (i <= j) {
            if (randomArray[i + 1] == randomArray[j + 1]) {
                cycle.push(randomArray[j + 1]);
            }
            i = i + 1;
            j = j + 1;
         }
         console.log(cycle);
       }
       i = start;
    }
   i = start;
 }  

それは私を返す必要があります。そして、私は同じことをするために正規表現したくありません

1,2
1,1
10,12

If array is ["a","d","z","e","g","h","a","d","z"]  

それから

output would be "a","d","z"

そして、それは最適なソリューションでなければなりません。これについて私に提案してください。少なくとも現在のコードの修正..

4

6 に答える 6

2

「トライ」ツリーのデータ構造を使用しました (詳細については、Google で検索してください)。ツリーはシーケンスごとに分岐します。1,1,1 が 2 回出現するため、解として 1,1,1 が見つかります。(数字が 2 つのシーケンスで繰り返されるのを止めたい場合は、トライの各ノードに対して一意のインデックスをカウントする必要があります)。

コードは次のとおりです。ランタイムは O(N^2) のようなもので、少し改善することができます。

var randomArray = [1,2,1,1,1,1,0,2,1,2,3,10,12,54,10,12]

var solve = function(a) {
    var trie = {};
    var sequence_set = {};
    for (var start = 0; start < a.length - 1; start += 1)  {
        var sub_trie = trie[a[start]] || {};
        trie[a[start]] = sub_trie;
        sequence = "" + a[start]
        for (var i = start + 1; i < a.length; i += 1) {
            sequence += "," + a[i]
            sub_trie[a[i]] = sub_trie[a[i]] || {};
            sub_trie = sub_trie[a[i]];
            var sub_trie_count = sub_trie.count || 0;
            sub_trie.count = sub_trie_count + 1;
            if (sub_trie_count >= 1) {
                sequence_set[sequence] = "found";
                console.log(sequence);
            }
        }
    }
    solution = "";
    for (sequence in sequence_set) {
        solution += sequence + ", ";
    }
    console.log(trie)
    return solution;
}

出力:

1,1 fiddle.jshell.net:37
1,1,1 fiddle.jshell.net:37
1,1 fiddle.jshell.net:37
2,1 fiddle.jshell.net:37
1,2 fiddle.jshell.net:37
10,12 fiddle.jshell.net:37
Object {0: Object, 1: Object, 2: Object, 3: Object, 10: Object, 12: Object, 54: Object}
 fiddle.jshell.net:45
于 2013-02-10T11:49:12.627 に答える
1
var randomArray = [1,2,1,1,1,1,0,2,1,2,3,10,12,54,10,12];

for(var i = 0; i < randomArray.length; i++) {
    var item = randomArray[i];
    var str  = "";    

    while(randomArray[i] == item) {
        str = str + " " + randomArray[i];   
        i++;
    }

    document.write(str + "<br />");
}

このJSFiddleを参照してください:http://jsfiddle.net/Ucgtm/

于 2013-02-10T06:40:52.407 に答える
1

Haskell で書いたばかりのソリューションを次に示します。(この言語がいかに簡潔であるかがわかります。) 以下のコードは、インタープリター コマンド ラインでの実装方法の例です。

import Data.List

findSequences list length
  | length >= 2 = repeatedPattern list length ++ findSequences list (length-1)
  | otherwise = []
    where repeatedPattern [] _ = []
          repeatedPattern list size
            | take size list `isInfixOf` drop size list = 
                take size list : repeatedPattern (tail list) size
            | otherwise = repeatedPattern (tail list) size

Prelude> :load "findSequences.hs"
[1 of 1] Main のコンパイル ( findSequences.hs、解釈済み )
OK、ロードされたモジュール: Main。
*Main> let randomArray = [1,2,1,1,1,1,0,2,1,2,3,10,12,54,10,12]
*Main> findSequences randomArray (floor $ (/2 ) $ fromIntegral (length randomArray))
[[1,2],[2,1],[1,1],[10,12]]
*Main> let array = ["a","d","z ","e","g","h","a","d","z"]
*Main> findSequences 配列 (floor $ (/2) $ fromIntegral (長さ配列))
[["a" ,"d","z"],["a","d"],["d","z"]]

于 2013-02-10T08:00:43.320 に答える
1

ここに私の解決策があります.@robert kingの(私が自分で問題に取り組んだ後に発見したように)のようですが、私の解決策は完全であり(重複するパターンを数えることはできません)、最適化されています(できる限り)。

また、オブジェクトのマップを返すので、それを列挙して、サイズ X のパターン、または Y 回繰り返されるパターンのみを引き出すことができます。


次の行(以下の関数を使用)

getPatterns([1,2,1,1,1,1,0,2,1,2,3,10,12,54,10,12]).showRepeated();

これが発生します。

1 2 found 2 times
2 1 found 2 times
1 1 found 2 times
10 12   found 2 times


コード

function getPatterns(input, generateAll) {
    var patternMap = new getPatterns.presentation();

    var generated = [];
    var patternObj;
    var start;
    //for each item
    for (var index = 0; index < input.length; ++index) {
        //open a new slot for a new pattern start at this index
        generated.push('');

        start = 0;
        //unless told to generate all
        //skip patterns that cant possibly be repeated
        //(i.e. longer than half the input length)
        if (!generateAll && generated.length > input.length / 2)
            start = generated.length - Math.floor(input.length / 2);

        //test patterns we have generated for this index
        for (var index2 = start; index2 < generated.length; ++index2) {
            //generate a fresh lot of patterns for this index
            generated[index2] += ' ' + input[index];

            //unless told to generate all, dismiss patterns of length 1
            if (!generateAll && index2 == generated.length - 1)
                break;

            //try to fetch a pre-existing pattern, O(1)
            patternObj = patternMap[generated[index2]];
            //if this is a new pattern
            if (!patternObj) {
                //generate an object
                patternMap[generated[index2]] = {
                    lastSeen : index,
                    count : 1,
                    size : generated.length - index2
                };
                continue;
            }

            //unless told to generate all, skip patterns that overlap with themselves
            if (!generateAll && index - patternObj.lastSeen < patternObj.size)
                continue;

            //this pattern has repeated! update the object data
            ++patternObj.count;
            patternObj.lastSeen = index;
        }
    }

    return patternMap;
}
//just for a function prototype
getPatterns.presentation = function() {};
getPatterns.presentation.prototype = {
    showRepeated : function() {
        var patternObj;
        for (var pattern in this) {
            patternObj = this[pattern];
            if (patternObj.count > 1)
                console.log(pattern + '\tfound ' + patternObj.count + ' times');
        }
    }
};
于 2013-07-20T08:02:38.033 に答える
0

「while」ループ内で i と j が同じ速度で増加しているため、「while」条件が満たされていないため、コードが無限ループに陥っている可能性があると思います。

于 2013-02-10T06:49:50.017 に答える
0

php で記述したい場合は、次のようになります。

外部のphpで配列を作成します<script>

$array=array("1","2","2","1".....);

$result = array_unique($array);

それで

var randomArray = <?php echo json_encode($result) ?>;

于 2013-02-10T06:38:07.603 に答える