Cari Tatasusunan Biasa Awalan Dua Tatasusunan

2657. Cari Tatasusunan Biasa Awalan Dua Tatasusunan

Kesukaran: Sederhana

Topik: Tatasusunan, Jadual Hash, Manipulasi Bit

Anda diberi dua 0-diindeks pilih atur integer A dan B panjang n.

A tatasusunan biasa awalan bagi A dan B ialah tatasusunan C supaya C[i] sama dengan kiraan nombor yang hadir pada atau sebelum indeks i dalam kedua-dua A dan B.

Kembalikan tatasusunan biasa awalan A dan B.

Jujukan n integer dipanggil permutasi jika ia mengandungi semua integer dari 1 hingga n tepat sekali.

Contoh 1:

• Input: A = [1,3,2,4], B = [3,1,2,4]
• Output: [0,2,3,4]
• Penjelasan: Pada i = 0: tiada nombor biasa, jadi C[0] = 0.
  • Pada i = 1: 1 dan 3 adalah biasa dalam A dan B, jadi C[1] = 2.
  • Pada i = 2: 1, 2, dan 3 adalah biasa dalam A dan B, jadi C[2] = 3.
  • Pada i = 3: 1, 2, 3, dan 4 adalah biasa dalam A dan B, jadi C[3] = 4.

Contoh 2:

• Input: A = [2,3,1], B = [3,1,2]
• Output: [0,1,3]
• Penjelasan: Pada i = 0: tiada nombor biasa, jadi C[0] = 0.
  • Pada i = 1: hanya 3 yang biasa dalam A dan B, jadi C[1] = 1.
  • Pada i = 2: 1, 2, dan 3 adalah biasa dalam A dan B, jadi C[2] = 3.

Kekangan:

• 1
• 1
• Adalah dijamin bahawa A dan B adalah kedua-duanya pilih atur bagi n integer.

Petunjuk:

1. Pertimbangkan untuk menyimpan tatasusunan frekuensi yang menyimpan kiraan kejadian setiap nombor sehingga indeks i.
2. Jika nombor berlaku dua kali, ini bermakna ia berlaku dalam kedua-dua A dan B kerana kedua-duanya adalah pilih atur jadi tambah satu pada jawapan.

Penyelesaian:

Kita boleh lelaran pada dua tatasusunan A dan B sambil menjejaki nombor yang telah berlaku pada atau sebelum indeks semasa dalam kedua-dua tatasusunan. Oleh kerana kedua-dua tatasusunan ialah pilih atur bagi set nombor yang sama, kita boleh menggunakan dua set cincang (atau tatasusunan) untuk menyimpan nombor yang telah muncul pada atau sebelum indeks semasa dalam kedua-dua tatasusunan. Untuk setiap indeks, kita boleh mengira nombor biasa yang telah muncul dalam kedua-dua tatasusunan sehingga titik itu.

Pendekatan Penyelesaian:

1. Gunakan dua tatasusunan untuk menjejaki kejadian nombor dalam kedua-dua A dan B sehingga indeks i.
2. Untuk setiap indeks i, semak sama ada A[i] dan B[i] pernah dilihat sebelum ini. Jika ya, tambahkan kiraan biasa.
3. Gunakan tatasusunan frekuensi untuk menjejaki kehadiran nombor dari 1 hingga n dalam kedua-dua tatasusunan.

Mari laksanakan penyelesaian ini dalam PHP: 2657. Cari Tatasusunan Biasa Awalan Dua Tatasusunan

<?php /**
 * @param Integer[] $A
 * @param Integer[] $B
 * @return Integer[]
 */
function findThePrefixCommonArray($A, $B) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$A = [1, 3, 2, 4];
$B = [3, 1, 2, 4];
print_r(findThePrefixCommonArray($A, $B)); // Output: [0, 2, 3, 4]

$A = [2, 3, 1];
$B = [3, 1, 2];
print_r(findThePrefixCommonArray($A, $B)); // Output: [0, 1, 3]
?>

Penjelasan:

1. Susun Kekerapan: Kami mengekalkan dua tatasusunan frekuensi, freqA dan freqB, di mana setiap indeks mewakili nombor dalam pilih atur.
   • Apabila kita menemui nombor dalam A[i] atau B[i], kita meningkatkan nilai yang sepadan dalam tatasusunan frekuensi.
2. Kiraan Biasa: Selepas mengemas kini tatasusunan kekerapan untuk kedua-dua A[i] dan B[i], kami menyemak setiap nombor jika ia telah muncul dalam kedua-dua tatasusunan sehingga indeks i. Jika ya, kami meningkatkan CommonCount.
3. Keputusan: Kiraan biasa disimpan dalam tatasusunan hasil untuk setiap indeks.

Contoh Panduan:

Untuk input:

$A = [1, 3, 2, 4];
$B = [3, 1, 2, 4];

• Pada i = 0: Tiada nombor sepunya lagi → C[0] = 0
• Pada i = 1: Nombor 1 dan 3 adalah biasa → C[1] = 2
• Pada i = 2: Nombor 1, 2, dan 3 adalah biasa → C[2] = 3
• Pada i = 3: Nombor 1, 2, 3, dan 4 adalah biasa → C[3] = 4

Output: [0, 2, 3, 4]

Kerumitan Masa:

• O(n²⁾: Untuk setiap indeks i, kami sedang menyemak setiap elemen dari 1 hingga n untuk melihat sama ada ia adalah perkara biasa, menjadikan penyelesaian ini kuadratik dalam kerumitan masa. Ini boleh diterima memandangkan kekangan n ≤ 50.

Ini harus berfungsi dalam kekangan yang diberikan dengan berkesan.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Cari Tatasusunan Biasa Awalan Dua Tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!