给出起始索引时，以循环方式查找数组的值

Question

我希望有人可以帮助解决一个小算法问题，即以“循环”方式找到数组的正确值。我的例子是javascript，虽然理论上它可以是任何语言。

这是场景：我有一个数字数组，以及一个“当前指针”，它是数组的某个索引值。我想传入一个“diff”整数值，可能是正数或负数。如果diff为负，则指针索引减小，循环回到数组的另一侧。如果为正，则指针索引增加，并且如果超出范围则循环回到数组的另一侧。

我在下面包含了一些示例调用来指示示例函数调用和预期输出。

var arr = [0, 1, 2, 3, 4];

// starting at current index, increase or
// decrease index of arr by "diff" amount
// and then return the value at that index

function getValue(arr, current, diff) {

    var newIndex;

    if ( diff >= 0 ) {
        // increase current value by diff
        // increments, in a circular fashion
    }
    else if ( diff < 0 ) {
        // decrease current value by diff
        // increments, in a circular fashion
    }

    return arr[newIndex];
}

// sample calls, with expected output

getValue(arr, 0, 2); // 2
getValue(arr, 0, 4); // 4
getValue(arr, 0, 5); // 0
getValue(arr, 0, 12); // 2
getValue(arr, 0, -1); // 4
getValue(arr, 0, -7); // 3

getValue(arr, 3, 2); // 0
getValue(arr, 3, 4); // 2
getValue(arr, 3, 5); // 3
getValue(arr, 3, 12); // 0
getValue(arr, 3, -1); // 2
getValue(arr, 3, -7); // 1

Answer 1

这是模数的概念很重要的时候：它基本上是除法的余数。您想要的是获取元素的匹配索引，而不管迭代同一个数组的次数。这有效地找到了数组长度的模数和要移动的步数（diff）：

function getValue(arr, current, diff) {

    var newIndex = (current + diff) % arr.length;

    // If the new index is negative, we just count backwards from the end of the array
    if (newIndex < 0)
      newIndex = arr.length + newIndex;

    return arr[newIndex];
}

上面的逻辑是：

1. 它决定它应该行进的数组前后多远。我们简单地加上current和diff
2. 使用模数运算符%来确定循环遍历数组之后的最终索引，直到没有剩余为止
3. 如果索引为负（如果我们向后移动则可能），那么我们只是将其视为“从数组末尾向后计数”

---

请参阅下面的概念验证：

var arr = [0, 1, 2, 3, 4];

function getValue(arr, current, diff) {

    var newIndex = (current + diff) % arr.length;
    
    // If the new index is negative, we just count backwards from the end of the array
    if (newIndex < 0)
      newIndex = arr.length + newIndex;
      
    console.log(newIndex);
    return arr[newIndex];
}

// sample calls, with expected output

getValue(arr, 0, 2); // 2
getValue(arr, 0, 4); // 4
getValue(arr, 0, 5); // 0
getValue(arr, 0, 12); // 2
getValue(arr, 0, -1); // 4
getValue(arr, 0, -7); // 3

getValue(arr, 3, 2); // 0
getValue(arr, 3, 4); // 2
getValue(arr, 3, 5); // 3
getValue(arr, 3, 12); // 0
getValue(arr, 3, -1); // 2
getValue(arr, 3, -7); // 1

Answer 2

var arr = [0, 1, 2, 3, 4];
function getValue(arr, current, diff) {
    if (diff >=0) {
        return arr[(current+diff) % arr.length];
    }
    else {
        return arr[(arr.length + ((current+diff) % arr.length)) % arr.length];
    }
}

console.log(getValue(arr, 0, 2)); // 2
console.log(getValue(arr, 0, 4)); // 4
console.log(getValue(arr, 0, 5)); // 0
console.log(getValue(arr, 0, 12)); // 2
console.log(getValue(arr, 0, -1)); // 4
console.log(getValue(arr, 0, -7)); // 3

console.log(getValue(arr, 3, 2)); // 0
console.log(getValue(arr, 3, 4)); // 2
console.log(getValue(arr, 3, 5)); // 3
console.log(getValue(arr, 3, 12)); // 0
console.log(getValue(arr, 3, -1)); // 2
console.log(getValue(arr, 3, -7)); // 1

var arr = [0, 1, 2, 3, 4];
function getValue(arr, current, diff) {
    if (diff >=0) {
        return arr[(current+diff) % arr.length];
    }
    else {
        return arr[(arr.length + ((current+diff) % arr.length)) % arr.length];
    }
}

console.log(getValue(arr, 0, 2)); // 2
console.log(getValue(arr, 0, 4)); // 4
console.log(getValue(arr, 0, 5)); // 0
console.log(getValue(arr, 0, 12)); // 2
console.log(getValue(arr, 0, -1)); // 4
console.log(getValue(arr, 0, -7)); // 3

console.log(getValue(arr, 3, 2)); // 0
console.log(getValue(arr, 3, 4)); // 2
console.log(getValue(arr, 3, 5)); // 3
console.log(getValue(arr, 3, 12)); // 0
console.log(getValue(arr, 3, -1)); // 2
console.log(getValue(arr, 3, -7)); // 1