2661. Pertama Baris atau Lajur Dicat Sepenuhnya

Kesukaran: Sederhana

Topik: Tatasusunan, Jadual Hash, Matriks

Anda diberi arr tatasusunan integer 0-diindeks dan tikar matriks m x n integer. arr dan mat kedua-duanya mengandungi semua integer dalam julat [1, m * n].

Telusuri setiap indeks i dalam arr bermula dari indeks 0 dan cat sel dalam tikar yang mengandungi arr integer[i].

Kembalikan indeks i terkecil di mana sama ada baris atau lajur akan dicat sepenuhnya dalam tikar.

Contoh 1:

• Input: arr = [1,3,4,2], tikar = [[1,4],[2,3]]
• Output: 2
• Penjelasan: Pergerakan ditunjukkan mengikut tertib, dan kedua-dua baris pertama dan lajur kedua matriks menjadi dicat sepenuhnya pada arr[2].

Contoh 2:

• Input: arr = [2,8,7,4,1,3,5,6,9], tikar = [[3,2,5],[1,4,6],[ 8,7,9]]
• Output: 3
• Penjelasan: Lajur kedua menjadi dicat sepenuhnya pada arr[3].

Kekangan:

• m == tikar.panjang
• n = tikar[i].panjang
• arr.panjang == m * n
• 1 5
• 1 5
• 1
• Semua integer arr adalah unik.
• Semua integer tikar adalah unik.

Petunjuk:

1. Bolehkah kita menggunakan tatasusunan frekuensi?
2. Praproses kedudukan nilai dalam matriks.
3. Lintas tatasusunan dan naikkan kekerapan baris dan lajur yang sepadan menggunakan kedudukan pra-diproses.
4. Jika kekerapan baris menjadi sama dengan bilangan lajur, atau sebaliknya kembalikan indeks semasa.

Penyelesaian:

Kita boleh ikut langkah ini:

Pendekatan

1. Pra-proses kedudukan elemen:

   • Pertama, kita perlu menyimpan kedudukan unsur dalam matriks. Kita boleh mencipta kamus (peta_kedudukan) yang memetakan setiap nilai dalam matriks kepada kedudukannya (baris, kol).

2. Susun Kekerapan:

   • Kami memerlukan dua tatasusunan frekuensi: satu untuk baris dan satu untuk lajur.
   • Semasa kita melalui tatasusunan arr, kita akan menambah kekerapan baris dan lajur masing-masing untuk setiap elemen.

3. Semak Baris atau Lajur Lengkap:

   • Selepas setiap kenaikan, semak jika mana-mana baris atau lajur dicat sepenuhnya (iaitu, kekerapannya mencapai saiz lajur atau baris matriks).
   • Jika ya, kembalikan indeks semasa.

4. Kembalikan keputusan:

   • Indeks di mana sama ada baris atau lajur dicat sepenuhnya ialah jawapan kami.

Langkah Terperinci

1. Buat peta kedudukan_peta untuk setiap nilai dalam tikar ke kedudukannya (baris, kol).
2. Buat tatasusunan row_count dan col_count untuk menjejak bilangan sel yang dicat dalam setiap baris dan lajur.
3. Melintasi arr dan untuk setiap elemen, kemas kini kiraan baris dan lajur masing-masing.
4. Jika pada bila-bila masa baris atau lajur dicat sepenuhnya, kembalikan indeks itu.

Mari laksanakan penyelesaian ini dalam PHP: 2661. Baris atau Lajur Dicat Sepenuhnya Pertama

<?php /**
 * @param Integer[] $arr
 * @param Integer[][] $mat
 * @return Integer
 */
function firstCompleteIndex($arr, $mat) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$arr = [1, 3, 4, 2];
$mat = [[1, 4], [2, 3]];
echo firstCompleteIndex($arr, $mat); // Output: 2

$arr = [2, 8, 7, 4, 1, 3, 5, 6, 9];
$mat = [[3, 2, 5], [1, 4, 6], [8, 7, 9]];
echo firstCompleteIndex($arr, $mat); // Output: 3
?>

Penjelasan:

1. Kedudukan pra-pemprosesan:

   • Kami membina position_map kamus di mana setiap nilai dalam tikar dipetakan ke kedudukannya (baris, kol). Ini membantu dalam mengakses terus kedudukan mana-mana nilai dalam masa tetap semasa traversal arr.

2. Pengiraan kekerapan:

   • Kami memulakan tatasusunan row_count dan col_count dengan sifar. Tatasusunan ini akan menjejaki berapa kali sel dalam baris atau lajur tertentu telah dicat.

3. Merentasi tatasusunan:

   • Untuk setiap nilai dalam arr, kami mencari kedudukannya dalam position_map, kemudian menambah bilangan baris dan lajur yang sepadan.
   • Selepas mengemas kini kiraan, kami menyemak sama ada mana-mana baris atau lajur telah mencapai saiz penuhnya (iaitu, row_count[$row] == n atau col_count[$col] == m). Jika ya, kami mengembalikan indeks semasa i.

4. Keputusan Pulangan:

   • Indeks pertama yang sama ada baris atau lajur dicat sepenuhnya dikembalikan.

Kerumitan Masa:

• Pra-pemprosesan: Kami membina peta_kedudukan dalam O(m * n).
• Traversal: Kami memproses setiap elemen arr (yang mempunyai panjang m * n), dan untuk setiap elemen, kami melakukan operasi masa tetap untuk mengemas kini dan menyemak frekuensi baris dan lajur, yang mengambil masa O( 1) masa.
• Secara keseluruhan, kerumitan masa ialah O(m * n).

Kerumitan Ruang:

• Kami menyimpan kedudukan semua elemen dalam position_map, dan kami menggunakan ruang O(m n) untuk tatasusunan frekuensi. Oleh itu, kerumitan ruang ialah O(m * n).

Penyelesaian ini harus cekap menangani masalah dalam kekangan yang diberikan.

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 Pertama Baris atau Lajur Dicat Sepenuhnya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!