代码之家 › 专栏 › 技术社区 › witherwind

在数组中获得唯一序列的最短方法

sequence arrays javascript

witherwind · 技术社区 · 8 年前

我有一个基于数组生成模式的javascript代码。

下面的数组:

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

将返回:

[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1]

但是,我希望简化模式,并且只获得唯一的序列,即:

[1, 1, 1, 1, -1, -1, -1, -1]

我能用什么方法做到这一点吗 slice() 或 filter() 是吗? 如果没有,那我怎么能有什么建议呢?

请注意,数组模式和唯一序列的长度是可变的。

3 回复 | 直到 8 年前

Luis felipe De jesus Munoz 8 年前

对不起,关于另一个答案。我跑得很快。

// Ask the original sequence as parameter
function uniqueSequence(originalSequence){

    return 
        originalSequence
        .map(function(value, index){                            // Get difference between each number.
            return value - originalSequence[index - 1];         // Somthing like [1,2,3,2,1] => [NaN, 1,1,-1,-1]
        })
        .toString()                                             // Parse that result to string format => "NaN,1,1,-1,-1"
        .match(/N((,[0-9-]+)*?)\1*$/)[1]                        // we look for the shortest pattern of comma-separated integers 
                                                                // (,\d+) starting right after "NaN" and repeating till 
                                                                // the end of the string. Result in something like => ",1,1,-1,-1"
        .substring(1)                                           // Remove the first comma => "1,1,-1,-1"                                    
        .split(',')                                             // Convert to array ["1","1","-1","-1"]
        .map(function(value){
            return parseInt(value);                             // Parse each element to integer [1,1,-1,-1]
        });
}

最短代码(ES6)

 f=_=>_.map((a,i)=>a-_[i-1]).toString().match(/N((,[0-9-]+)*?)\1*$/)[1].substring(1).split`,`.map(a=>~~a)

f=_=>_.map((a,i)=>a-_[i-1]).toString().match(/N((,[0-9-]+)*?)\1*$/)[1].substring(1).split`,`.map(a=>~~a)

// Ask the original sequence as parameter
function uniqueSequence(originalSequence){

    return originalSequence
        .map(function(value, index){                            // Get difference between each number.
            return value - originalSequence[index - 1];         // Somthing like [1,2,3,2,1] => [NaN, 1,1,-1,-1]
        })
        .toString()                                             // Parse that result to string format => "NaN,1,1,-1,-1"
        .match(/N((,[0-9-]+)*?)\1*$/)[1]                       // we look for the shortest pattern of comma-separated integers 
                                                                // (,\d+) starting right after "NaN" and repeating till 
                                                                // the end of the string. Result in something like => ",1,1,-1,-1"
        .substring(1)                                           // Remove the first comma => "1,1,-1,-1"                                    
        .split(',')                                             // Convert to array ["1","1","-1","-1"]
        .map(function(value){
            return parseInt(value);                             // Parse each element to integer [1,1,-1,-1]
        });
}

console.log(f([1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 1]))
console.log(uniqueSequence([1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 1]))

Royal Wares 8 年前

您可以通过两个函数一起工作来实现这一点,其概念是我们要从原始模式中取一个增量较大的部分,并查看它是否在原始模式中均匀地重复。

function getUniquePattern(pattern) {
    // Test an incrementally large slice of the original pattern.
    for (i = 0; i < pattern.length; i++) {
        // Take a slice to test
        var attempt = pattern.slice(0, i);

        // Check if the slice repeats perfectly against the pattern
        if(sliceIsRepeatable(attempt, pattern)){
            // Return the matched pattern
            return attempt;
        }
    }

    // Return an empty array for failures
    return [];
}

function sliceIsRepeatable(slice, pattern) {
    // Slice length must be a multiple of the pattern's length
    if(pattern.length % slice.length !== 0 ) return false;

    for (i = 0; i < pattern.length; i++) {
        j = i % slice.length;
        if(pattern[i] !== slice[j]) {
            return false;
        }
    }

    return true;
}

getUniquePattern([1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1]);

Keith 8 年前

不确定这是不是最短的路,但很简单。希望很容易理解,我放了一些评论来帮助展示它在做什么。

const test1 = [1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1];
const test2 = [4, -1, 4, -1, 4, -1, 4, -1];

function getSeq(a) {
  //lets try diving the array by length / 2, then each
  //time use bigger and bigger chunks.
  for (let chunks = a.length / 2; chunks >= 1; chunks --) {
    const chunksize = a.length / chunks;
    //can we divide equally?.    
    if (chunksize % 1 !== 0) continue;
    //lets compare all chunks are the same
    let found = true;
    for (let lpchunk = 1; lpchunk < chunks; lpchunk ++) {   
      for (let offset = 0; offset < chunksize; offset ++) {
        if (a[offset] !== a[offset + lpchunk * chunksize]) {
          found = false;
          break;
        }
      }
    }
    //we have found a duplicate lets return..
    if (found) {
      const dups = [];
      for (let offset = 0; offset < chunksize; offset ++) {
        dups.push(a[offset]);
      }
      return dups;
    }
  }
}

console.log(getSeq(test1).join(", "));
console.log(getSeq(test2).join(", "));