Squares of a Sorted Array

Q: Berapa kompleksitas waktu dari Squares of a Sorted Array?

Solusi dengan dua pointer berjalan dalam waktu O(n) : setiap nilai dikuadratkan dan ditempatkan satu kali. Menguadratkan lalu mengurutkan membutuhkan biaya O(n log n) . Keduanya menggunakan memori O(n) untuk hasilnya.

MudahTwo pointers Pengurutan

+10

Kamu mendapatkan array bilangan bulat nums yang diurutkan dalam urutan tidak menurun. Array ini dapat berisi nilai negatif. Kuadratkan setiap nilai dan kembalikan hasil kuadratnya sebagai array baru, yang juga diurutkan dalam urutan tidak menurun.

Fungsi

sortedSquares(nums: integer-array) → integer-array

numsinteger-array: array bilangan bulat yang sudah diurutkan, termasuk bilangan negatif
Mengembalikaninteger-array: kuadrat dari setiap nilai, diurutkan dalam urutan tidak menurun

Batasan

1 ≤ nums.length ≤ 4000
-10⁴ ≤ nums[i] ≤ 10⁴
nums diurutkan dalam urutan tidak menurun.

Contoh

Input: nums = [-6, -2, 1, 3, 7]
Output: [1, 4, 9, 36, 49]
Penjelasan: Hasil kuadrat dalam urutan awal adalah 36, 4, 1, 9, dan 49. Nilai negatif -6 dan -2 menghasilkan kuadrat yang besar, jadi pengurutan memindahkan 36 mendekati akhir: [1, 4, 9, 36, 49].

Input: nums = [-9, -4, -1]
Output: [1, 16, 81]
Penjelasan: Setiap nilai bernilai negatif, jadi hasil kuadratnya muncul dalam urutan terbalik: 81, 16, 1 menjadi [1, 16, 81].

Pertanyaan lanjutan

Menghitung kuadrat dan mengurutkan memerlukan O(n log n). Bisakah kamu melakukannya dalam O(n)?

Petunjuk

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

0 dari 3 dibuka

Solusi

Operasi kuadrat membalik urutan nilai negatif, sehingga hasil kuadrat tidak terurut. Namun, nilai kuadrat terbesar selalu berasal dari salah satu ujung nums. Bandingkan kedua ujungnya, tempatkan nilai kuadrat yang lebih besar di bagian belakang hasil, lalu bergerak ke arah tengah.

Kuadratkan, lalu urutkan

Intuisi

Buat array baru yang berisi kuadrat setiap nilai, lalu urutkan. Pengurutan menempatkan kuadrat dalam urutan yang benar, dari mana pun asalnya. Pengurutan membutuhkan biaya O(n log n) dan mengabaikan urutan yang diberikan kepadamu.

Algoritma

Buat array dengan x * x untuk setiap x dalam nums.
Urutkan array tersebut berdasarkan urutan angka dari kecil ke besar, lalu kembalikan.

def sortedSquares(nums):
    return sorted(x * x for x in nums)

Dua pointer dari kedua ujung

Intuisi

Kuadrat membesar seiring jarak dari 0. Dalam array yang sudah diurutkan, nilai yang paling jauh dari 0 berada di kedua ujung, nilai paling negatif di sebelah kiri dan nilai paling positif di sebelah kanan, jadi kuadrat terbesar adalah nums[left]² atau nums[right]². Tulis nilai yang lebih besar di bagian belakang hasil, lalu geser penunjuk itu ke dalam. Bagian yang tersisa di antara kedua penunjuk tetap terurut, jadi hal yang sama berlaku pada setiap langkah.

Pada [-6, -2, 1, 3, 7]: 49 mengalahkan 36 dan ditempatkan di posisi terakhir. Lalu 36 mengalahkan 9, 9 mengalahkan 4, 4 mengalahkan 1, dan nilai 1 mengisi posisi 0. Setiap nilai ditempatkan satu kali: waktu O(n), dan hasilnya adalah satu-satunya array tambahan.

Algoritma

Buat array hasil dengan panjang n. Atur left ke 0 dan right ke n-1.
Telusuri posisi pos dari n-1 turun hingga 0.
Bandingkan nums[left]² dengan nums[right]².
Tulis kuadrat yang lebih besar pada pos dan geser pointer tersebut satu langkah ke dalam.
Kembalikan hasilnya.

def sortedSquares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    # the largest square left is always at one of the two ends
    for pos in range(n - 1, -1, -1):
        left_sq = nums[left] * nums[left]
        right_sq = nums[right] * nums[right]
        if left_sq > right_sq:
            result[pos] = left_sq
            left += 1
        else:
            result[pos] = right_sq
            right -= 1
    return result

Jebakan dan kasus tepi

Mengisi hasil dari depan. Kotak terkecil berada di tempat nilai-nilai berpotongan dengan 0, yang bisa berada di mana saja di tengah; bagian ujung hanya menunjukkan nilai terbesar.
Membandingkan nums[left] dengan nums[right], bukan kuadratnya. -6 lebih kecil daripada 3, tetapi kuadratnya lebih besar, jadi [-6, 3] menghasilkan [36, 9].
Berhenti saat left bertemu right. Masih ada satu nilai yang belum ditempatkan; lakukan perulangan pada setiap posisi, atau gunakan left <= right.
Dalam JavaScript dan TypeScript, sort() tanpa pembanding mengurutkan angka sebagai teks, sehingga [1, 4, 36, 9] menjadi [1, 36, 4, 9]. Berikan (a, b) => a - b.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Squares of a Sorted Array?

Solusi dengan dua pointer berjalan dalam waktu O(n): setiap nilai dikuadratkan dan ditempatkan satu kali. Menguadratkan lalu mengurutkan membutuhkan biaya O(n log n). Keduanya menggunakan memori O(n) untuk hasilnya.

Bisakah kamu mengisi hasilnya dari bagian depan?

Ya, tetapi kamu harus menemukan terlebih dahulu titik saat nilai-nilai melewati 0, misalnya dengan binary search. Lalu, dua pointer bergerak ke luar dari titik itu. Mengisi dari belakang menghindari pencarian, karena kedua ujungnya sudah diketahui sejak awal.

Apakah Squares of a Sorted Array merupakan masalah merge?

Ya. Nilai negatif yang dikuadratkan, dibaca dari kanan ke kiri, membentuk satu list terurut, dan nilai nonnegatif yang dikuadratkan membentuk list lainnya. Menggabungkan keduanya adalah langkah merge dalam merge sort, itulah sebabnya proses ini dapat dilakukan dalam satu kali lintasan linear.

def sortedSquares(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

nums = [-6, -2, 1, 3, 7]

Output yang diharapkan

[1, 4, 9, 36, 49]