文章背景：
在復(fù)習(xí)算法及數(shù)據(jù)結(jié)構(gòu)時，找到了面試筆試題目，下面我們來看看題目：
（學(xué)習(xí)視頻分享：java教學(xué)視頻）
在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)?。輸入一個數(shù)組,求出這個數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對1000000007取模的結(jié)果輸出。 即輸出P%1000000007
輸入描述:
題目保證輸入的數(shù)組中沒有的相同的數(shù)字
數(shù)據(jù)范圍：
對于%50的數(shù)據(jù),size<=10^4
對于%75的數(shù)據(jù),size<=10^5
對于%100的數(shù)據(jù),size<=2*10^5
分析：
這道題目很好直接求解，不過時間復(fù)雜度在o(n*n) ,?最開始拿到這題沒經(jīng)過思考，直接dp寫完了，然后發(fā)現(xiàn)，dp還不如直接求解，都是o(n*n)的復(fù)雜度，dp還占用了2*10^5的空間，下面是直接，求法和dp ,都超時了。
（更多相關(guān)面試題推薦：java面試題及答案）
代碼分享：
//直接求法 ,超時
public class solution{
public static int sum;
public static int InversePairs(int [] array) {
dp(array);
return sum;
}
public static void dp(int []array){
for(int i = array.length - 1 ; i > 0 ; i --){
for(int j = i - 1 ; j >= 0 ; j--){
if(array[j] > array[i]){
sum += 1;
}
}
sum %= 1000000007;
}
}
}public class solution{
//一維數(shù)組dp
public static int sum;
public static int InversePairs(int [] array) {
dp(array);
return sum;
}
public static int count[] = new int[200004];
public static void dp(int []array){
for(int i = array.length - 1 ; i > 0 ; i --){
for(int j = i - 1 ; j >= 0 ; j--){
if(array[j] > array[i]){
count[j] = count[j+1]+1;
}else {
count[j] = count[j+1];
}
}
sum += count[0];
sum %= 1000000007;
for(int k = 0 ; k < array.length ; k ++)
count[k] = 0;
}
}
}dp在這里都是多余的，
下面是歸并排序解決問題，不了解歸并排序可以看我前一篇博客 歸并排序：
public class solution{
//歸并排序AC
public static int cnt ;
public static int InversePairs(int [] array) {
if(array != null){
RecusionSorted(array,0,array.length - 1);
}
return cnt%1000000007;
}
public static void MegerArray(int[] data, int start, int mid, int end) {
int temp[] = new int[end-start+1];
int i = mid;
int j = end;
int m = mid+1;
int z = 0;
while(j >= m && i >= start) {
if(data[i] > data[j]) {
temp[z++] = data[i--];
cnt += (j-mid)%1000000007;
cnt %= 1000000007;
}else {
temp[z++] = data[j--];
}
}
while(j >= m) {
temp[z++] = data[j--];
}
while(i >= start) {
temp[z++] = data[i--];
}
for(int k = start ; k <= end ; k ++) {
data[k] = temp[end - k];
}
}
public static void RecusionSorted(int data[] , int start , int end ) {
if(start < end) {
int mid = (start + end) >> 1;
RecusionSorted(data,start,mid);
RecusionSorted(data,mid+1,end);
MegerArray(data,start,mid,end);
}
}
}相關(guān)推薦：java入門教程
Atas ialah kandungan terperinci java面試之歸并排序的應(yīng)用. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
Alat AI Hot
Undress AI Tool
Gambar buka pakaian secara percuma
Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik
AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.
Clothoff.io
Penyingkiran pakaian AI
Video Face Swap
Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!
Artikel Panas
Alat panas
Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma
SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan
Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa
Dreamweaver CS6
Alat pembangunan web visual
SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)
Bagaimana menangani transaksi di Java dengan JDBC?
Aug 02, 2025 pm 12:29 PM
Untuk mengendalikan transaksi JDBC dengan betul, anda mesti terlebih dahulu mematikan mod komit automatik, kemudian melakukan pelbagai operasi, dan akhirnya melakukan atau mengembalikan semula hasilnya; 1. Panggil Conn.SetAutOcommit (palsu) untuk memulakan transaksi; 2. Melaksanakan pelbagai operasi SQL, seperti memasukkan dan mengemaskini; 3. Panggil Conn.Commit () jika semua operasi berjaya, dan hubungi conn.rollback () jika pengecualian berlaku untuk memastikan konsistensi data; Pada masa yang sama, cuba-dengan-sumber harus digunakan untuk menguruskan sumber, mengendalikan pengecualian dengan betul dan menutup sambungan untuk mengelakkan kebocoran sambungan; Di samping itu, adalah disyorkan untuk menggunakan kolam sambungan dan menetapkan mata simpan untuk mencapai rollback separa, dan menyimpan urus niaga sesingkat mungkin untuk meningkatkan prestasi.
Bagaimana untuk bekerja dengan kalendar di Jawa?
Aug 02, 2025 am 02:38 AM
Gunakan kelas dalam pakej Java.Time untuk menggantikan kelas lama dan kelas kalendar; 2. Dapatkan tarikh dan masa semasa melalui LocalDate, LocalDateTime dan Tempatan Tempatan; 3. Buat tarikh dan masa tertentu menggunakan kaedah (); 4. Gunakan kaedah tambah/tolak untuk meningkatkan dan mengurangkan masa; 5. Gunakan zoneddatetime dan zonid untuk memproses zon waktu; 6. Format dan parse date string melalui DateTimeFormatter; 7. Gunakan segera untuk bersesuaian dengan jenis tarikh lama apabila perlu; pemprosesan tarikh di java moden harus memberi keutamaan untuk menggunakan java.timeapi, yang memberikan jelas, tidak berubah dan linear
Membandingkan kerangka Java: Spring Boot vs Quarkus vs Micronaut
Aug 04, 2025 pm 12:48 PM
Pra-formancetartuptimemoryusage, quarkusandmicronautleadduetocompile-timeprocessingandgraalvsupport, withquarkusoftenperforminglightbetterine serverless scenarios.tyvelopecosyste,
Memahami Pelabuhan Rangkaian dan Firewall
Aug 01, 2025 am 06:40 AM
NetworkPortsandFireWallSworkTogethertoenableCommunicationWileensuringsecurity.1.networkportsarevirtualendpointsNumbered0-655 35, Withwell-KnownportsLike80 (http), 443 (https), 22 (ssh), dan25 (smtp) identitispecificservices.2.portsoperateovertcp (boleh dipercayai, c
Bagaimana pengumpulan sampah berfungsi di java?
Aug 02, 2025 pm 01:55 PM
Koleksi Sampah Java (GC) adalah mekanisme yang secara automatik menguruskan ingatan, yang mengurangkan risiko kebocoran ingatan dengan menuntut semula objek yang tidak dapat dicapai. 1.GC menghakimi kebolehcapaian objek dari objek akar (seperti pembolehubah stack, benang aktif, medan statik, dan lain -lain), dan objek yang tidak dapat dicapai ditandakan sebagai sampah. 2. Berdasarkan algoritma penandaan tanda, tandakan semua objek yang dapat dicapai dan objek yang tidak ditandai. 3. Mengamalkan strategi pengumpulan generasi: Generasi Baru (Eden, S0, S1) sering melaksanakan MinorGC; Orang tua melakukan kurang tetapi mengambil masa lebih lama untuk melakukan MajorGC; Metaspace Stores Metadata kelas. 4. JVM menyediakan pelbagai peranti GC: SerialGC sesuai untuk aplikasi kecil; ParallelGC meningkatkan throughput; CMS mengurangkan
Membandingkan Java Build Tools: Maven vs Gradle
Aug 03, 2025 pm 01:36 PM
GradleisthebetterChoiceFormostNewProjectSduetoitSsuperiorflexibility, Prestasi, danModernToolingSupport.1.Gradle'sGroovy/KOT lindslismoreconciseandexpressivethanmaven'sverbosexml.2.GradleOutPerformsMaveninBuildSpeedWithIncrementalcompilation, BuildCac
Pergi dengan contoh penangguhan yang dijelaskan
Aug 02, 2025 am 06:26 AM
Defer digunakan untuk melaksanakan operasi tertentu sebelum fungsi pulangan, seperti sumber pembersihan; Parameter dinilai dengan serta-merta apabila menangguhkan, dan fungsi-fungsi dilaksanakan mengikut urutan terakhir (LIFO); 1. Pelbagai penahanan dilaksanakan dalam urutan terbalik pengisytiharan; 2. Biasanya digunakan untuk pembersihan yang selamat seperti penutupan fail; 3. Nilai pulangan yang dinamakan boleh diubah suai; 4. Ia akan dilaksanakan walaupun panik berlaku, sesuai untuk pemulihan; 5. Elakkan penyalahgunaan menangguhkan gelung untuk mengelakkan kebocoran sumber; Penggunaan yang betul boleh meningkatkan keselamatan kod dan kebolehbacaan.
Menggunakan jenis html `input` untuk data pengguna
Aug 03, 2025 am 11:07 AM
Memilih jenis htmlinput yang betul dapat meningkatkan ketepatan data, meningkatkan pengalaman pengguna, dan meningkatkan kebolehgunaan. 1. Pilih jenis input yang sepadan mengikut jenis data, seperti teks, e -mel, tel, nombor dan tarikh, yang secara automatik boleh menyemak dan menyesuaikan diri dengan papan kekunci; 2. Gunakan HTML5 untuk menambah jenis baru seperti URL, Warna, Julat dan Carian, yang dapat memberikan kaedah interaksi yang lebih intuitif; 3. Gunakan pemegang tempat dan sifat -sifat yang diperlukan untuk meningkatkan kecekapan dan ketepatan pengisian bentuk, tetapi harus diperhatikan bahawa pemegang tempat tidak dapat menggantikan label.
