Find Pivot Index

Q: Berapa kompleksitas waktu Find Pivot Index?

Solusi total dan jumlah kumulatif berjalan dalam waktu O(n) , satu kali lintasan untuk menjumlahkan array dan satu kali untuk memindainya, dengan ruang tambahan O(1) . Menghitung ulang kedua sisi pada setiap indeks membutuhkan O(n²) .

MudahPrefix sum

+10

Kamu mendapatkan sebuah array bilangan bulat nums. Indeks pivot adalah indeks yang jumlah nilainya di sebelah kiri sama dengan jumlah nilainya di sebelah kanan. Nilai pada pivot itu sendiri tidak termasuk di kedua sisi, dan sisi yang tidak memiliki nilai memiliki jumlah 0.

Kembalikan indeks pivot paling kiri, atau -1 jika tidak ada indeks yang merupakan pivot.

Fungsi

pivotIndex(nums: integer-array) → integer

numsinteger-array: array bilangan bulat yang akan diseimbangkan
Mengembalikaninteger: indeks pivot paling kiri, atau -1 jika tidak ada

Batasan

1 ≤ nums.length ≤ 10⁴
-1000 ≤ nums[i] ≤ 1000

Contoh

Input: nums = [3, 1, 5, 2, 2]
Output: 2
Penjelasan: Pada indeks 2, jumlah di kiri 3 + 1 = 4 seimbang dengan jumlah di kanan 2 + 2 = 4. Indeks 0 menghasilkan 0 berbanding 10 dan indeks 1 menghasilkan 3 berbanding 9, jadi 2 adalah pivot paling kiri.

Input: nums = [1, 2, 3]
Output: -1
Penjelasan: Ketiga kandidat menghasilkan 0 melawan 5, 1 melawan 3, dan 3 melawan 0. Tidak ada indeks yang seimbang, jadi jawabannya adalah -1.

Pertanyaan lanjutan

Bisakah kamu menemukan pivot paling kiri dengan membaca setiap nilai hanya sekali, tanpa menjumlahkan totalnya terlebih dahulu? Berapa banyak memori yang dibutuhkan?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Menghitung ulang kedua jumlah pada setiap indeks membutuhkan biaya O(n²). Jumlah kiri bertambah satu nilai pada setiap langkah, dan jumlah kanan adalah sisa dari total. Jadi, satu kali lintasan untuk menghitung total dan satu kali lintasan dengan jumlah kiri yang terus diperbarui akan menemukan pivot paling kiri, dengan dua angka di memori.

Jumlahkan kedua sisi pada setiap indeks

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Untuk setiap indeks, jumlahkan nilai-nilai sebelumnya dan nilai-nilai sesudahnya, lalu bandingkan. Mencoba indeks dari kiri ke kanan menjadikan kecocokan pertama sebagai pivot paling kiri. Di salah satu ujung, satu perulangan berjalan nol kali dan jumlahnya tetap 0, itulah sebabnya [4, -4, 9] menghasilkan 2.

Setiap indeks menjumlahkan n-1 nilai lainnya. Dengan 10.000 nilai, jumlahnya hampir 100 juta penjumlahan, dan sebagian besar mengulang penjumlahan dari indeks sebelumnya.

Algoritma

Lakukan perulangan i pada setiap indeks nums.
Jumlahkan nums[0] hingga nums[i-1] sebagai jumlah kiri.
Jumlahkan nums[i+1] hingga nilai terakhir sebagai jumlah kanan.
Jika kedua jumlah sama, kembalikan i.
Jika tidak ada indeks yang cocok, kembalikan -1.

def pivotIndex(nums):
    n = len(nums)
    for i in range(n):
        left = 0
        for j in range(i):
            left += nums[j]
        right = 0
        for j in range(i + 1, n):
            right += nums[j]
        if left == right:
            return i
    return -1

Array jumlah awalan

Intuisi

Array prefix sum melakukan penjumlahan satu kali. Misalkan prefix[k] adalah jumlah dari k nilai pertama, dengan prefix[0] = 0; untuk [3, 1, 5, 2, 2], hasilnya adalah [0, 3, 4, 9, 11, 13]. Sisi kiri indeks i adalah prefix[i], dan sisi kanannya adalah prefix[n] - prefix[i+1]. Pada indeks 2, nilainya adalah 4 dibandingkan dengan 13 - 9 = 4, sehingga menjadi titik pivot.

Satu kali lintasan membangun array dan setiap pemeriksaan membutuhkan waktu konstan: waktu O(n), dengan n+1 angka tambahan di memori.

Algoritma

Buat prefix dengan panjang n+1 dan prefix[0] = 0.
Isi: prefix[k+1] = prefix[k] + nums[k].
Untuk setiap indeks i, baca jumlah di kiri sebagai prefix[i] dan jumlah di kanan sebagai prefix[n] - prefix[i+1].
Kembalikan i pertama yang membuat keduanya sama, atau -1 setelah perulangan.

def pivotIndex(nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values.
    prefix = [0] * (n + 1)
    for k in range(n):
        prefix[k + 1] = prefix[k] + nums[k]
    for i in range(n):
        left = prefix[i]
        right = prefix[n] - prefix[i + 1]
        if left == right:
            return i
    return -1

Jumlah total dan jumlah berjalan dari kiri

Intuisi

Pada indeks i, pendekatan prefix membaca prefix[i], prefix[i+1], dan prefix[n]. Yang terakhir adalah total, yang tidak pernah berubah, sedangkan dua lainnya adalah jumlah berjalan yang bisa kamu hitung sambil menelusuri array. Jadi, simpan total dan satu jumlah kiri, bukan array.

Setiap nilai berada di sebelah kiri i, pada i, atau di sebelah kanan i, sehingga jumlah kanan adalah total - left - nums[i]. Lakukan perbandingan sebelum menambahkan nums[i] ke left, agar jumlah kiri tidak pernah mencakup nilai yang sedang kamu uji. Pada contoh pertama, totalnya 13, dan indeks 2 memberikan 4, sama dengan 13 - 4 - 5 = 4.

Dua kali penelusuran membutuhkan waktu O(n), dan dua angka membutuhkan ruang O(1).

Algoritma

Jumlahkan setiap nilai ke dalam total.
Atur left menjadi 0.
Untuk setiap indeks i, jika left sama dengan total - left - nums[i], kembalikan i.
Jika tidak, tambahkan nums[i] ke left lalu lanjutkan.
Jika perulangan berakhir, kembalikan -1.

def pivotIndex(nums):
    total = sum(nums)
    left = 0
    for i, value in enumerate(nums):
        # Everything that is not on the left and not nums[i] is on the right.
        if left == total - left - value:
            return i
        left += value
    return -1

Jebakan dan kasus tepi

Menambahkan nums[i] ke jumlah sisi kiri sebelum perbandingan. Sisi kiri kemudian mencakup nilai pivot, dan [3, 1, 5, 2, 2] tidak lagi menemukan indeks 2.
Menghitung sisi kanan sebagai total - left. Perhitungan itu memasukkan nums[i] ke sisi kanan, jadi kurangi juga nilai tersebut.
Melewatkan indeks 0 atau indeks terakhir. Jumlah sisi yang kosong adalah 0, jadi [1, -1, 1] mengembalikan 0 dan [4, -4, 9] mengembalikan 2.
Lupa bahwa array Lua dan R dimulai dari 1. Kembalikan i-1 agar jawabannya berupa indeks berbasis 0.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Find Pivot Index?

Solusi total dan jumlah kumulatif berjalan dalam waktu O(n), satu kali lintasan untuk menjumlahkan array dan satu kali untuk memindainya, dengan ruang tambahan O(1). Menghitung ulang kedua sisi pada setiap indeks membutuhkan O(n²).

Apakah Find Pivot Index bisa diselesaikan dengan dua pointer?

Tidak selalu. Pemindaian dari kedua ujung yang selalu memperluas sisi yang lebih kecil mengasumsikan bahwa penambahan nilai akan membuat sisi tersebut lebih besar. Nilai di sini bisa turun hingga -1000, sehingga sisi bisa menyusut saat bertambah, dan pointer bisa bergerak melewati pivot yang sebenarnya.

Berapa indeks pivot dari array yang memiliki satu elemen?

Nilainya 0. Kedua sisi dari satu-satunya elemen itu kosong, dan sisi yang kosong berjumlah 0, jadi kedua sisi sama. Solusi jumlah berjalan mengembalikan 0 pada perbandingan pertamanya.

def pivotIndex(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [3, 1, 5, 2, 2]

Output yang diharapkan

Find Pivot Index

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Jumlahkan kedua sisi pada setiap indeks

Array jumlah awalan

Jumlah total dan jumlah berjalan dari kiri

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa