Mündəricat
Problem bəyanat
Məhdudlaşdırılmış Massivdə Verilmiş İndeksdə Maksimum Dəyər problemi LeetCode Həlli sizə üç müsbət tam ədəd verildiyini deyir: n, indeksvə maksimum məbləğ. Siz massiv qurmaq istəyirsiniz nömrə(0 indeksli) aşağıdakı şərtləri təmin edir:
- ədədlər.uzunluq == n
- nums [i] birdir müsbət harada tam ədəd 0 <= i < n.
- abs(numlar[i]-numlar[i+1]) <= 1 hara 0 <= i < n-1.
- The bütün elementlərin cəmi of nömrə keçmir maksimum məbləğ.
- ədədlər[indeks] is maximized.
Qayıtmaq ədədlər[indeks] qurulmuş massivdən.
Qeyd edək ki, abs (x) bərabərdir x if x >= 0və -x başqa cür.
Məhdudlaşdırılmış massivdə verilmiş indeksdə maksimum dəyər üçün nümunə LeetCode Həlli:
Test işi 1:
Input:
n = 8
indeks = 3
maksimum cəm = 14
Çıxış:
3
Test işi 2:
Input:
n = 7
indeks = 4
maksimum cəm = 8
Çıxış:
2
Məhdudlaşdırılmış massivdə verilmiş indeksdə maksimum dəyər üçün izahat LeetCode Həlli:
i) Birinci hal üçün massiv kimi ola bilərik [0, 1, 2, 3, 2, 1, 0, 0]. Beləliklə, indeks 3-də maksimum dəyər 3. Bu, bütün məhdudiyyətləri təmin edən maksimum dəyərdir.
i) İkinci hal üçün massiv kimi ola bilərik [0, 0, 0, 1, 2, 1, 0]. Beləliklə, indeks 4-də maksimum dəyər 2. Bu, bütün məhdudiyyətləri təmin edən maksimum dəyərdir.
Yanaşma
Idea:
Əvvəlcə edirik maxsum -= n,
onda bütün elementlər yalnız etibarlı olmalıdır A[i]>=0.
Arasında son nəticəni ikili axtarış edirik Zaman və sağ,
hara sol = 0 və sağ = maxsum.
Hər bir test üçün, əgər minimum məbləği yoxlayırıq A[indeks] = a.
Minimum hal olardı A[indeks] zirvəsidir A.
Bu, sol tərəfdəki arifmetik ardıcıllıqdır A[indeks] fərqlə 1.
Bu, həm də sağdakı arifmetik ardıcıllıqdır A[indeks] fərqlə -1.
Solda, A[0] = maks(a – indeks, 0),
Sağda, A[n-1] = maks(a – ((n-1) – indeks), 0),
{b, b+1, ….a} arifmetik ardıcıllığın cəmi,
bərabərdir (a + b) * (a – b + 1)/ 2.
Kodu
Məhdudlaşdırılmış massivdə verilmiş indeksdə maksimum dəyər üçün Java proqramı
class Solution {
public int maxValue(int n, int index, int maxSum) {
maxSum -= n;
int left = 0, right = maxSum, mid;
while (left < right) {
mid = (left + right + 1) / 2;
if (test(n, index, mid) <= maxSum)
left = mid;
else
right = mid - 1;
}
return left + 1;
}
private long test(int n, int index, int a) {
int b = Math.max(a - index, 0);
long res = (long)(a + b) * (a - b + 1) / 2;
b = Math.max(a - ((n - 1) - index), 0);
res += (long)(a + b) * (a - b + 1) / 2;
return res - a;
}
}
Məhdudlaşdırılmış massivdə verilmiş indeksdə maksimum dəyər üçün C++ proqramı
class Solution {
public:
int maxValue(int n, int index, int maxSum) {
maxSum -= n;
int left = 0, right = maxSum, mid;
while (left < right) {
mid = (left + right + 1) / 2;
if (test(n, index, mid) <= maxSum)
left = mid;
else
right = mid - 1;
}
return left + 1;
}
long test(int n, int index, int a) {
int b = max(a - index, 0);
long res = long(a + b) * (a - b + 1) / 2;
b = max(a - ((n - 1) - index), 0);
res += long(a + b) * (a - b + 1) / 2;
return res - a;
}
};
Məhdudlaşdırılmış massivdə verilmiş indeksdə maksimum dəyər üçün Python proqramı
class Solution(object):
def maxValue(self, n, index, maxSum):
def test(a):
b = max(a - index, 0)
res = (a + b) * (a - b + 1) / 2
b = max(a - ((n - 1) - index), 0)
res += (a + b) * (a - b + 1) / 2
return res - a
maxSum -= n
left, right = 0, maxSum
while left < right:
mid = (left + right + 1) / 2
if test(mid) <= maxSum:
left = mid
else:
right = mid - 1
return left + 1
Məhdudlaşdırılmış Massivdə Verilmiş İndeksdə Maksimum Dəyər üçün Mürəkkəblik Təhlili LeetCode Həlli
Zamanın mürəkkəbliyi
Hər bir dəyər üçün biz məbləği yoxlaya bilərik O (1) düsturdan istifadə zamanı. Beləliklə, zaman mürəkkəbliyi O(log(maksimum cəmi)).
Kosmik Mürəkkəblik
Burada heç bir əlavə yerdən istifadə etmirik. Kosmik mürəkkəblik belədir O (1).
Referans: https://en.wikipedia.org/wiki/Binary_search_algorithm
