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

确定整数数组中最长的方差周期

algorithm arrays javascript

AnonymousSB · 技术社区 · 6 年前

我正在尝试编写一个函数,它将识别数字数组中最长的方差周期。方差开始于前一个数字高于当前数字,结束于下一个数字与当前数字相同;但是,如果方差没有结束,则假定方差开始于后两个数字。

例如: [10, 5, 3, 11, 8, 9, 9, 2, 10] 此数组中最长的方差周期是 [5, 3, 11, 8, 9] ,或者只是 5 (长度)。在这种情况下,当以下数字与当前数字相同时,方差结束。 9 .

我写的函数在这种情况下是有效的;但是,当整个数组都有变化时,它就不起作用了,例如 [10, 5, 10, 5, 10, 5, 10, 5, 10] 回报 8 ,应该是什么时候 九 .

如果前一个数字是数字,则始终低于或高于方差。 2 因为它从未结束。例如 [2, 4, 6, 8] 和 [8, 6, 4, 2] .

我知道整个数组方差的问题可以通过启动 for 在0处循环,但其他情况将变为无效。非常感谢您的帮助。

不用再多费吹灰之力,我的代码是:

function findVariance(numbers) {
    if ([0,1].includes(numbers.length)) return numbers.length;

    const variance = [[0]];
    let greater = numbers[1] > numbers[0];
    let lesser = numbers[1] < numbers[0];

    for (let i = 1; i < numbers.length; i++) {
        let previous = variance.length - 1;
        let previousVarianceGroup = variance[previous];
        let previousVarianceGroupValue = previousVarianceGroup[previousVarianceGroup.length - 1];

        if (greater) {
            if (numbers[i] <  numbers[previousVarianceGroupValue]) {
                previousVarianceGroup.push(i);
                greater = false;
                lesser = true;
            } else {
                greater = numbers[i] < numbers[previousVarianceGroupValue];
                lesser = numbers[i] < numbers[previousVarianceGroupValue];
                variance.push([previousVarianceGroupValue, i]);
            }
        } else if (lesser) {
            if (numbers[i] > numbers[previousVarianceGroupValue]) {
                previousVarianceGroup.push(i);
                greater = true;
                lesser = false;
            } else {
                greater = numbers[i] > numbers[previousVarianceGroupValue];
                lesser = numbers[i] > numbers[previousVarianceGroupValue];
                variance.push([previousVarianceGroupValue, i]);
            }
        } else {
            greater = numbers[i] > numbers[previousVarianceGroupValue];
            lesser = numbers[i] < numbers[previousVarianceGroupValue];
            variance.push([previousVarianceGroupValue, i]);
        }
    }

    const result = [];

    for (let i = 0; i < variance.length; i++) {
        result[i] = variance[i].length;
    }

    result.sort();

    return result[result.length - 1];
}

console.log(findVariance([10, 5, 3, 11, 8, 9, 9, 2, 10]));
console.log(findVariance([10, 5, 10, 5, 10, 5, 10, 5, 10]));
console.log(findVariance([2, 4, 6, 8]));

2 回复 | 直到 6 年前

puddi 6 年前

以下是我所得到的(尽我所能理解这个问题)

function calculateVariance(arr) {
    // trivial cases
    if (arr.length <= 1) { return arr.length; }

    // store the difference between each pair of adjacent numbers
    let diffs = [];
    for (let i = 1; i < arr.length; i++) {
        diffs.push(arr[i] - arr[i - 1]);
    }

    let max = 0;

    // if the difference between two numbers is 0, they're the same.
    // the base max variance encountered is 1, otherwise it's 2.
    // the boolean zen here is that diffs[0] is falsy when it's 0, and truthy otherwise
    let count = diffs[0] ? 2 : 1;

    // go through the array of differences,
    // and count how many in a row are alternating above/below zero.
    for (i = 1; i < diffs.length; i++) {
        if ((diffs[i] < 0 !== diffs[i - 1] < 0) && diffs[i] && diffs[i - 1]) {
            count++;
        } else {
            max = Math.max(count, max);
            // see above
            count = diffs[i] ? 2 : 1;
        }
    }

    // account for the maximum variance happening at the end
    return Math.max(count, max);
}

Jonas Wilms 6 年前

你有点过于复杂了,只要一个元素等于下一个元素,就增加一个计数器,重置为相等:

 const counts = [];

 let count = 0;
 for(let i = 0; i < numbers.length - 1; i++) {
   if(numbers[i] === numbers[i + 1]) {
     counts.push(count);
     count = 0;
   } else {
      count++;
  }
}

 counts.push(count);

return counts.sort()[counts.length - 1];