Bagaimana untuk melaksanakan tatasusunan tidak menurun dalam java

Penerangan Masalah

Memandangkan tatasusunan yang mengandungi n integer, tugas anda adalah untuk menyemak sama ada ia boleh menjadi tidak turun dengan mengubah suai paling banyak satu elemen. Tatasusunan tidak menurun memenuhi tatasusunan[i-1]

Sampel 1:

ⅰ Input: [4,2,3]

ⅱ Output: Benar

ⅲ Penerangan : Anda boleh menukar nombor pertama 4 kepada 1, dan dapatkan [1,2,3] sebagai tatasusunan tidak menurun

Contoh 2:

ⅰ Input: [ 4,2,1]

ⅱ Output: Salah

ⅲ Penerangan: Tatasusunan tidak boleh dibuat tidak menurun dengan mengubah suai paling banyak satu elemen.

Analisis idea penyelesaian masalah

a memenuhi syarat, pengubahsuaian unsur dapat memenuhi syarat, dan pengubahsuaian unsur tidak dapat memenuhi syarat. Untuk kes pertama, hanya merentasi tatasusunan untuk melihat sama ada setiap item dalam tatasusunan lebih besar daripada atau sama dengan item sebelumnya. Jika ya, kembalikan benar. Untuk kes kedua, anda boleh menghitung tatasusunan nombor[i] untuk diubah suai, dan kemudian semak sama ada nombor sebelum tatasusunan[i] tidak berkurangan dan sama ada nombor selepas tatasusunan[i] tidak berkurangan, Akhir sekali Anda juga harus menyemak sama ada array[i-1] adalah benar (tidak perlu menyemak sama ada array[i] adalah pada sempadan), jika benar Kemudian anda boleh menukar tatasusunan[i] kepada sebarang nombor antara tatasusunan[i-1] dan tatasusunan[i+1] untuk menjadikan tatasusunan itu tatasusunan tidak menurun Ini adalah kes 2. Kembalikan benar jika ia tidak benar untuk semua i , maka ia adalah kes tiga dan mengembalikan palsu. Kerumitan masa untuk melakukan ini ialah O(n^2), dan kerumitan ruang tambahan ialah O(1).

b. Apakah syarat yang dipenuhi untuk menukar nombor menjadi tatasusunan tidak menurun selepas mengubah suainya? Jelas sekali, tatasusunan sedemikian harus memenuhi syarat bahawa terdapat hanya sepasang nombor bersebelahan yang tidak memenuhi syarat tidak tolak, iaitu, hanya terdapat satu i unik (1array[i], Ia boleh ditegaskan bahawa jika terdapat berbilang i seperti itu, tatasusunan asal tidak boleh menjadi tatasusunan tidak menurun dengan mengubah suai paling banyak satu nombor. Jadi bolehkah mana-mana tatasusunan yang memenuhi syarat ini memenuhi bukan tolak dengan mengubah suai nombor? Tidak, contohnya [2,4,1,3], hanya 4,1 yang bersebelahan tidak memenuhi bukan menurun, tetapi ia tidak boleh menjadi tidak menurun dengan menukar hanya satu nombor. Malah, jika terdapat hanya satu i yang memenuhi tatasusunan[i-1]>tatasusunan[i], maka nombor yang hendak diubah suai mestilah antara dua tatasusunan nombor[i-1] dan tatasusunan[i], maka Anda boleh menggunakan pendekatan sebelumnya dan membuat pertimbangan berasingan ke atas kedua-dua situasi tersebut. Tambahan pula, memandangkan tatasusunan[i-1]>tatasusunan[i] adalah benar hanya untuk i, semua nombor bersebelahan lain memenuhi syarat tidak menurun, jadi untuk tatasusunan[i-1] Dikatakan bahawa tatasusunan sebelum dan selepasnya memenuhi syarat tidak menurun, dan perkara yang sama berlaku untuk tatasusunan[i]. Oleh itu, anda hanya perlu menilai sama ada dua tatasusunan sebelum dan selepas boleh disambungkan kepada tatasusunan tidak menurun. Secara khusus, jika nombor yang akan diubah suai ialah tatasusunan[i-1], maka anda hanya perlu menilai sama ada tatasusunan[i-2]tatasusunan[i], dan syarat untuk akhirnya mengembalikan benar ialah tatasusunan[i-1], tatasusunan[i] ialah sempadan, atau tatasusunan[i-2]

Program rujukan

Versi Java:

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan tatasusunan tidak menurun dalam java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!