Поиск значения массива по кругу, когда задается начальный индекс

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

Это когда концепция модуль важна: это в основном остаток от деления.То, что вы хотите, это получить соответствующий индекс элемента, независимо от того, сколько раз итераций по одному и тому же массиву.Это эффективно находит модуль длины массива и количество шагов (разность), которые вы хотите переместить:

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. Используйте оператор модуля %, чтобы определить конечный индекс, в котором мы находимся после цикла по массиву столько раз, сколько сможем, пока не останется остатокleft
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