Давайте назовем данную функцию sum .Как описано, вы бы назвали его sum(array, i, j), и он вернул бы сумму array[i] + ... + array[j-1].Я предполагаю, что диапазон исключает индекс в j сам, но рассуждение то же самое, если оно будет включено.
Давайте также назовем k количество нулей в B .
Теперь вы можете использовать двоичный поиск для поиска крайнего левого 0 в B , сравнивая sum(A, 0, i) с sum(B, 0, i) при изменении i в соответствии с методом двоичного поиска.Затем, когда найден самый низкий индекс, для которого эти суммы не равны, то вы знаете, что B [i] равно нулю, а в O (logn) времени.
Итак, присвойте соответствующее (ненулевое) значение от A [i] до B [i] .Затем повторите это k раз.Поскольку k является постоянной величиной, это не влияет на сложность времени: O (klogn) все еще O (logn) , когда k являетсяконстанта, как например 2.
Вот реализация в JavaScript с примером ввода, и k = 2 .
// Implementation of the hidden function, which (contrary to this implementation)
// should run in constant time
function sum(arr, i, j) {
result = 0;
while (i < j) {
result += arr[i++];
}
return result;
}
// example
let a = [3,2,6,7,1,9,8,5];
let b = [3,2,0,7,1,9,0,5];
let n = a.length;
let k = 2;
for (let times = 0; times < k; times++) {
// Apply binary search
let low = 0;
let high = n;
while (low < high) {
let mid = (low + high + 1) >> 1;
if (sum(a, 0, mid) == sum(b, 0, mid)) {
low = mid;
} else {
high = mid - 1;
}
}
// Found index where zero is at:
b[low] = a[low];
}
console.log(b);
Когда k неизвестно
... тогда оно не является постоянным, а переменным.В этом случае временная сложность становится равной O ((k + 1) logn) , что составляет O (klogn) , и цикл должен продолжаться до тех пор, пока поиск больше не найдет ноль (при(k + 1) th итерация):
// Implementation of the hidden function, which (contrary to this implementation)
// should run in constant time
function sum(arr, i, j) {
result = 0;
while (i < j) {
result += arr[i++];
}
return result;
}
// example
let a = [3,2,6,7,1,9,8,5];
let b = [3,2,0,7,1,9,0,5];
let n = a.length;
// no definition of k here
while (true) {
let low = 0;
let high = n;
while (low < high) {
let mid = (low + high + 1) >> 1;
if (sum(a, 0, mid) == sum(b, 0, mid)) {
low = mid;
} else {
high = mid - 1;
}
}
if (low >= n) break; // no zero found
// Found index where zero is at:
b[low] = a[low];
}
console.log(b);