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

我使用了“trie”树数据结构（谷歌获取更多信息）。每个序列的树分支。因为 1,1,1 出现了两次，所以它找到了 1,1,1 作为解。（如果你想阻止一个数字在两个序列中重复，你需要针对树的每个节点计算唯一索引）。

这是代码：运行时应该类似于 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，解释)
好的，模块已加载：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 array (floor $(/2) $ fromIntegral (length array))
[["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

如果你想要它在 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 回答
0

我认为您的代码可能会进入无限循环，因为 i 和 j 在“while”循环内以相同的速率增加，因此“while”条件没有得到满足。

于 2013-02-10T06:49:50.017 回答