Transformasi Kedudukan Tatasusunan

1331. Transformasi Kedudukan Suatu Tatasusunan

Kesukaran: Mudah

Topik: Tatasusunan, Jadual Hash, Isih

Memandangkan tatasusunan integer arr, gantikan setiap elemen dengan kedudukannya.

Pangkat mewakili betapa besar elemen itu. Pangkat mempunyai peraturan berikut:

• Kedudukan ialah integer bermula dari 1.
• Lebih besar elemen, lebih besar pangkatnya. Jika dua elemen adalah sama, pangkatnya mestilah sama.
• Pangkat hendaklah sekecil mungkin.

Contoh 1:

• Input: arr = [40,10,20,30]
• Output: [4,1,2,3]
• Penjelasan: 40 ialah elemen terbesar. 10 adalah yang terkecil. 20 adalah yang kedua terkecil. 30 ialah yang ketiga terkecil.

Contoh 2:

• Input: arr = [100,100,100]
• Output: [1,1,1]
• Penjelasan: Elemen yang sama berkongsi kedudukan yang sama.

Contoh 3:

• Input: arr = [37,12,28,9,100,56,80,5,12]
• Output: [5,3,4,2,8,6,7,1,3]

Kekangan:

• 0 <= arr.length <= 10⁵
• -10⁹ <= arr[i] <= 10⁹

Petunjuk:

1. Gunakan tatasusunan sementara untuk menyalin tatasusunan dan mengisihnya.
2. Kedudukan setiap elemen ialah bilangan elemen unik yang lebih kecil daripadanya dalam tatasusunan yang diisih tambah satu.

Penyelesaian:

Kita boleh memecahkannya kepada langkah-langkah berikut:

1. Salin dan susun tatasusunan: Ini membantu dalam menentukan kedudukan setiap elemen unik.
2. Gunakan peta cincang untuk menetapkan kedudukan kepada elemen: Memandangkan berbilang elemen boleh berkongsi nilai yang sama, peta cincang (tatasusunan bersekutu dalam PHP) akan membantu memetakan setiap elemen kepada kedudukannya.
3. Ganti elemen asal dengan kedudukannya: Menggunakan peta cincang, kita boleh menggantikan setiap elemen dalam tatasusunan asal dengan kedudukannya yang sepadan.

Mari laksanakan penyelesaian ini dalam PHP: 1331. Transformasi Kedudukan Suatu Tatasusunan

  
  
  Penjelasan:




Salin dan susun tatasusunan:


Kami mencipta salinan tatasusunan input $sorted dan menyusunnya. Ini membantu dalam menentukan pangkat setiap elemen unik.



Tetapkan pangkat kepada elemen:


Kami mengulangi tatasusunan yang diisih dan menggunakan peta cincang $rank untuk menyimpan kedudukan setiap elemen unik.
Kami menggunakan isset untuk menyemak sama ada elemen telah diberikan pangkat. Jika tidak, kami menetapkan kedudukan semasa dan menaikkannya.



Ganti elemen dengan pangkatnya:


Kami kemudiannya mengulangi tatasusunan asal dan menggantikan setiap elemen dengan pangkat yang sepadan dengan mencarinya dalam peta cincang $rank.





  
  
  Kerumitan Masa:



Mengisih tatasusunan mengambil masa O(n log n), dengan n ialah saiz tatasusunan.
Menetapkan kedudukan dan menggantikan nilai memerlukan O(n).
Kerumitan masa keseluruhan ialah O(n log n).


Penyelesaian ini mengendalikan tatasusunan besar dengan cekap sambil mengekalkan kesederhanaan.

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 Transformasi Kedudukan Tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!