Semak Jika N dan Gandaannya Wujud

1346. Semak Jika N dan Doublenya Wujud

Kesukaran: Mudah

Topik: Tatasusunan, Jadual Hash, Dua Penunjuk, Carian Binari, Isih

Memandangkan susunan tatasusunan integer, semak sama ada wujud dua indeks i dan j supaya :

• i != j
• 0 <= i, j < arr.panjang
• arr[i] == 2 * arr[j]

Contoh 1:

• Input: arr = [10,2,5,3]
• Output: benar
• Penjelasan: Untuk i = 0 dan j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Contoh 2:

• Input: arr = [3,1,7,11]
• Output: palsu
• Penjelasan: Tiada i dan j yang memenuhi syarat.

Kekangan:

• 2 <= arr.length <= 500
• -10³ <= arr[i] <= 10³

Petunjuk:

1. Gelung daripada i = 0 kepada arr.length, mengekalkan dalam jadual hash elemen tatasusunan daripada [0, i - 1].
2. Pada setiap langkah gelung semak sama ada kita telah melihat elemen 2 * arr[i] setakat ini.
3. Juga semak jika kita telah melihat arr[i] / 2 sekiranya arr[i] % 2 == 0.

Penyelesaian:

Kami boleh menggunakan jadual cincang (tatasusunan bersekutu) untuk menjejaki elemen yang telah kami temui semasa melelakan tatasusunan. Ideanya adalah untuk menyemak setiap elemen arr[i] jika dua kali ganda (iaitu, 2 * arr[i]) atau separuh (iaitu, arr[i] / 2 jika ia nombor genap) telah ditemui.

Berikut ialah penyelesaian langkah demi langkah:

Pelan:

1. Lelaran melalui tatasusunan.
2. Untuk setiap elemen arr[i], semak sama ada kita telah melihat 2 * arr[i] atau arr[i] / 2 (jika arr[i] genap) dalam jadual cincang.
3. Jika mana-mana syarat dipenuhi, kembalikan benar.
4. Jika tidak, tambahkan arr[i] pada jadual cincang dan teruskan ke elemen seterusnya.
5. Jika tiada padanan ditemui pada penghujungnya, balas palsu.

Mari laksanakan penyelesaian ini dalam PHP: 1346. Semak Jika N dan Doublenya Wujud

  
  
  Penjelasan:




Jadual Hash: Kami menggunakan tatasusunan bersekutu $hashTable untuk menyimpan elemen yang kami temui setakat ini.

Syarat Pertama: Untuk setiap elemen arr[i], kami menyemak sama ada arr[i] * 2 wujud dalam jadual cincang.

Keadaan Kedua: Jika elemen genap, kami menyemak sama ada arr[i] / 2 wujud dalam jadual cincang.

Menambah pada Jadual Hash: Selepas menyemak, kami menambah arr[i] pada jadual cincang untuk rujukan masa hadapan.

Kembali: Jika kami menemui padanan, kami segera kembali benar. Jika tiada padanan ditemui selepas gelung, kami mengembalikan palsu.



  
  
  Kerumitan Masa:



Kerumitan masa ialah O(n), dengan n ialah panjang tatasusunan. Ini kerana setiap elemen diproses sekali dan menyemak atau menambah elemen dalam jadual cincang mengambil masa yang tetap secara purata.



  
  
  Kerumitan Ruang:



Kerumitan ruang ialah O(n) disebabkan storan yang diperlukan untuk jadual cincang.


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 Semak Jika N dan Gandaannya Wujud. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!