java面試題之?dāng)?shù)組中的逆序?qū)?/h1>
更新時間：2019年03月05日 08:17:52 作者：水的化合物的專欄
這篇文章主要為大家詳細介紹了java面試題之?dāng)?shù)組中的逆序?qū)?，具有一定的參考價值，感興趣的小伙伴們可以參考一下
題目：在數(shù)組中的兩個數(shù)字如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)Α］斎胍粋€數(shù)組，求出這個數(shù)組中的逆序?qū)Φ目倲?shù)
例如在數(shù)組｛7，5，6，4｝中，一共存在5對逆序?qū)?，分別是｛7，6｝，｛7，5｝，｛7，4｝，｛6，4｝，｛5，4｝。
看到這個題目，我們的第一反應(yīng)就是順序掃描整個數(shù)組。每掃描到一個數(shù)組的時候，逐個比較該數(shù)字和它后面的數(shù)字的大小。如果后面的數(shù)字比它小，則這兩個數(shù)字就組成一個逆序?qū)Α＜僭O(shè)數(shù)組中含有n個數(shù)字。由于每個數(shù)字都要和O(n）個數(shù)字做比較，因此這個算法的時間復(fù)雜度為O(n2)。我們嘗試找找更快的算法。
我們以數(shù)組｛7，5，6，4｝為例來分析統(tǒng)計逆序?qū)Φ倪^程，每次掃描到一個數(shù)字的時候，我們不能拿它和后面的每一個數(shù)字做比較，否則時間復(fù)雜度就是O(n2)因此我們可以考慮先比較兩個相鄰的數(shù)字。
如下圖所示，我們先把數(shù)組分解稱兩個長度為2的子數(shù)組，再把這兩個子數(shù)組分別茶城兩個長度為1的子數(shù)組。接下來一邊合并相鄰的子數(shù)組，一邊統(tǒng)計逆序?qū)Φ臄?shù)目。在第一對長度為1的子數(shù)組｛7｝，｛5｝中7大于5，因此｛7，5｝組成一個逆序?qū)ΑＭ瑯釉诘诙﹂L度為1的子數(shù)組｛6｝，｛4｝中也有逆序?qū)Γ?，4｝。由于我們已經(jīng)統(tǒng)計了這兩隊子數(shù)組內(nèi)部逆序?qū)?，因此需要把這兩對子數(shù)組排序，以免在以后的統(tǒng)計過程中再重復(fù)統(tǒng)計。
接下來我們統(tǒng)計兩個長度為2的子數(shù)組之間的逆序?qū)Α?/p>
我們先用兩個指針分別指向兩個子數(shù)組的末尾，并每次比較兩個指針指向的數(shù)字。如果第一個子數(shù)組中的數(shù)字大于第二個子數(shù)組中的數(shù)字，則構(gòu)成逆序?qū)?，并且逆序?qū)Φ臄?shù)目等于第二個子數(shù)組中的剩余數(shù)字的個數(shù)。如果第一個數(shù)組中的數(shù)字小于或等于第二個數(shù)組中的數(shù)字，則不構(gòu)成逆序?qū)?。每一次比較的時候，我們都把較大的數(shù)字從后往前復(fù)制到一個輔助數(shù)組中去，確保輔助數(shù)組中的數(shù)字是遞增排序的。在把較大的數(shù)字復(fù)制到數(shù)組之后，把對應(yīng)的指針向前移動一位，接著來進行下一輪的比較。
經(jīng)過前面詳細的討論，我們可以總結(jié)出統(tǒng)計逆序?qū)Φ倪^程：先把數(shù)組分隔成子數(shù)組，先統(tǒng)計出子數(shù)組內(nèi)部的逆序?qū)Φ臄?shù)目，然后再統(tǒng)計出兩個相鄰子數(shù)組之間的逆序?qū)Φ臄?shù)目。在統(tǒng)計逆序?qū)Φ倪^程中，還需要對數(shù)組進行排序。如果對排序算法很熟悉，我們不難發(fā)現(xiàn)這個排序的過程就是歸并排序。
static int count = 0;
// 將有二個有序數(shù)列a[first...mid]和a[mid...last]合并。
static void mergearray(int a[], int first, int mid, int last, int temp[]) {
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n) {
if (a[i] > a[j]) {
// 左數(shù)組比右數(shù)組大
temp[k++] = a[j++];
// 因為如果a[i]此時比右數(shù)組的當(dāng)前元素a[j]大，
// 那么左數(shù)組中a[i]后面的元素就都比a[j]大
// 【因為數(shù)組此時是有序數(shù)組】
count += mid - i + 1;
} else {
temp[k++] = a[i++];
}
}
while (i <= m) {
temp[k++] = a[i++];
}
while (j <= n) {
temp[k++] = a[j++];
}
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
static void mergesort(int a[], int first, int last, int temp[]) {
if (first < last) {
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); // 左邊有序
mergesort(a, mid + 1, last, temp); // 右邊有序
mergearray(a, first, mid, last, temp); // 再將二個有序數(shù)列合并
}
}
static void mergeSort(int a[]) {
int[] p = new int[a.length];
mergesort(a, 0, a.length - 1, p);
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
-
使用Java創(chuàng)建數(shù)據(jù)透視表并導(dǎo)出為PDF的方法
數(shù)據(jù)透視分析是一種強大的工具，可以幫助我們從大量數(shù)據(jù)中提取有用信息并進行深入分析，本文將介紹如何使用Java來構(gòu)建PivotTable以及實現(xiàn)數(shù)據(jù)透視分析，并將其導(dǎo)出為PDF 2023-10-10
-
SpringBoot使用@EnableAutoConfiguration實現(xiàn)自動配置詳解
你有想過SpringBoot為什么能夠自動的幫我們創(chuàng)建一個Bean對象么？或許在我們使用的時候只需要在自己自定義的配置文件中加入@Bean對象就可以，但SpringBoot是如何來創(chuàng)建的呢 2022-08-08
-
idea2020.1.3 手把手教你創(chuàng)建web項目的方法步驟
這篇文章主要介紹了idea 2020.1.3 手把手教你創(chuàng)建web項目的方法步驟，文中通過圖文介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧 2020-08-08
-
這篇文章主要介紹了Spring MVC 請求處理流程詳解,本文分步驟結(jié)合實例代碼給大家介紹的非常詳細,感興趣的朋友一起看看吧 2025-04-04
-
Java通過Timer與TimerTask實現(xiàn)定時任務(wù)調(diào)度方式
本文介紹了如何在Java中使用`Timer`和`TimerTask`類來實現(xiàn)定時任務(wù)調(diào)度,`Timer`類用于創(chuàng)建計時器并安排任務(wù),而`TimerTask`類用于定義具體的任務(wù),文章詳細介紹了這兩個類的方法和使用示例,包括創(chuàng)建任務(wù)、安排任務(wù)、取消任務(wù)等操作,通過一個簡單的例子 2024-12-12
-
這篇文章主要介紹了Spring解決泛型擦除的思路，本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下 2024-01-01
-
有時候我們有多個項目需要使用多個版本JDK，本文主要介紹了Mac安裝多個JDK并實現(xiàn)動態(tài)切換，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧 2023-07-07
-
jdk1.5 版本新增了JUC并發(fā)編程包,極大的簡化了傳統(tǒng)的多線程開發(fā),下面這篇文章主要介紹了Java線程池的四種拒絕策略的相關(guān)資料,文中通過實例代碼介紹的非常詳細，需要的朋友可以參考下 2022-04-04
-
Java編程實現(xiàn)基于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索完整代碼
這篇文章主要介紹了Java編程實現(xiàn)基于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索完整代碼，具有一定借鑒價值，需要的朋友可以了解下。 2017-12-12
-
springMVC在restful風(fēng)格的性能優(yōu)化方案
這篇文章主要介紹了springMVC在restful風(fēng)格的性能優(yōu)化方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教 2021-08-08
最新評論
題目：在數(shù)組中的兩個數(shù)字如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)Α］斎胍粋€數(shù)組，求出這個數(shù)組中的逆序?qū)Φ目倲?shù)
例如在數(shù)組｛7，5，6，4｝中，一共存在5對逆序?qū)?，分別是｛7，6｝，｛7，5｝，｛7，4｝，｛6，4｝，｛5，4｝。
看到這個題目，我們的第一反應(yīng)就是順序掃描整個數(shù)組。每掃描到一個數(shù)組的時候，逐個比較該數(shù)字和它后面的數(shù)字的大小。如果后面的數(shù)字比它小，則這兩個數(shù)字就組成一個逆序?qū)Α＜僭O(shè)數(shù)組中含有n個數(shù)字。由于每個數(shù)字都要和O(n）個數(shù)字做比較，因此這個算法的時間復(fù)雜度為O(n2)。我們嘗試找找更快的算法。
我們以數(shù)組｛7，5，6，4｝為例來分析統(tǒng)計逆序?qū)Φ倪^程，每次掃描到一個數(shù)字的時候，我們不能拿它和后面的每一個數(shù)字做比較，否則時間復(fù)雜度就是O(n2)因此我們可以考慮先比較兩個相鄰的數(shù)字。
如下圖所示，我們先把數(shù)組分解稱兩個長度為2的子數(shù)組，再把這兩個子數(shù)組分別茶城兩個長度為1的子數(shù)組。接下來一邊合并相鄰的子數(shù)組，一邊統(tǒng)計逆序?qū)Φ臄?shù)目。在第一對長度為1的子數(shù)組｛7｝，｛5｝中7大于5，因此｛7，5｝組成一個逆序?qū)ΑＭ瑯釉诘诙﹂L度為1的子數(shù)組｛6｝，｛4｝中也有逆序?qū)Γ?，4｝。由于我們已經(jīng)統(tǒng)計了這兩隊子數(shù)組內(nèi)部逆序?qū)?，因此需要把這兩對子數(shù)組排序，以免在以后的統(tǒng)計過程中再重復(fù)統(tǒng)計。
接下來我們統(tǒng)計兩個長度為2的子數(shù)組之間的逆序?qū)Α?/p>
我們先用兩個指針分別指向兩個子數(shù)組的末尾，并每次比較兩個指針指向的數(shù)字。如果第一個子數(shù)組中的數(shù)字大于第二個子數(shù)組中的數(shù)字，則構(gòu)成逆序?qū)?，并且逆序?qū)Φ臄?shù)目等于第二個子數(shù)組中的剩余數(shù)字的個數(shù)。如果第一個數(shù)組中的數(shù)字小于或等于第二個數(shù)組中的數(shù)字，則不構(gòu)成逆序?qū)?。每一次比較的時候，我們都把較大的數(shù)字從后往前復(fù)制到一個輔助數(shù)組中去，確保輔助數(shù)組中的數(shù)字是遞增排序的。在把較大的數(shù)字復(fù)制到數(shù)組之后，把對應(yīng)的指針向前移動一位，接著來進行下一輪的比較。
經(jīng)過前面詳細的討論，我們可以總結(jié)出統(tǒng)計逆序?qū)Φ倪^程：先把數(shù)組分隔成子數(shù)組，先統(tǒng)計出子數(shù)組內(nèi)部的逆序?qū)Φ臄?shù)目，然后再統(tǒng)計出兩個相鄰子數(shù)組之間的逆序?qū)Φ臄?shù)目。在統(tǒng)計逆序?qū)Φ倪^程中，還需要對數(shù)組進行排序。如果對排序算法很熟悉，我們不難發(fā)現(xiàn)這個排序的過程就是歸并排序。
static int count = 0;
// 將有二個有序數(shù)列a[first...mid]和a[mid...last]合并。
static void mergearray(int a[], int first, int mid, int last, int temp[]) {
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n) {
if (a[i] > a[j]) {
// 左數(shù)組比右數(shù)組大
temp[k++] = a[j++];
// 因為如果a[i]此時比右數(shù)組的當(dāng)前元素a[j]大，
// 那么左數(shù)組中a[i]后面的元素就都比a[j]大
// 【因為數(shù)組此時是有序數(shù)組】
count += mid - i + 1;
} else {
temp[k++] = a[i++];
}
}
while (i <= m) {
temp[k++] = a[i++];
}
while (j <= n) {
temp[k++] = a[j++];
}
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
static void mergesort(int a[], int first, int last, int temp[]) {
if (first < last) {
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); // 左邊有序
mergesort(a, mid + 1, last, temp); // 右邊有序
mergearray(a, first, mid, last, temp); // 再將二個有序數(shù)列合并
}
}
static void mergeSort(int a[]) {
int[] p = new int[a.length];
mergesort(a, 0, a.length - 1, p);
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
-
使用Java創(chuàng)建數(shù)據(jù)透視表并導(dǎo)出為PDF的方法
數(shù)據(jù)透視分析是一種強大的工具，可以幫助我們從大量數(shù)據(jù)中提取有用信息并進行深入分析，本文將介紹如何使用Java來構(gòu)建PivotTable以及實現(xiàn)數(shù)據(jù)透視分析，并將其導(dǎo)出為PDF2023-10-10 -
SpringBoot使用@EnableAutoConfiguration實現(xiàn)自動配置詳解
你有想過SpringBoot為什么能夠自動的幫我們創(chuàng)建一個Bean對象么？或許在我們使用的時候只需要在自己自定義的配置文件中加入@Bean對象就可以，但SpringBoot是如何來創(chuàng)建的呢2022-08-08 -
idea2020.1.3 手把手教你創(chuàng)建web項目的方法步驟
這篇文章主要介紹了idea 2020.1.3 手把手教你創(chuàng)建web項目的方法步驟，文中通過圖文介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08 - 這篇文章主要介紹了Spring MVC 請求處理流程詳解,本文分步驟結(jié)合實例代碼給大家介紹的非常詳細,感興趣的朋友一起看看吧2025-04-04
-
Java通過Timer與TimerTask實現(xiàn)定時任務(wù)調(diào)度方式
本文介紹了如何在Java中使用`Timer`和`TimerTask`類來實現(xiàn)定時任務(wù)調(diào)度,`Timer`類用于創(chuàng)建計時器并安排任務(wù),而`TimerTask`類用于定義具體的任務(wù),文章詳細介紹了這兩個類的方法和使用示例,包括創(chuàng)建任務(wù)、安排任務(wù)、取消任務(wù)等操作,通過一個簡單的例子2024-12-12 - 這篇文章主要介紹了Spring解決泛型擦除的思路，本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2024-01-01
- 有時候我們有多個項目需要使用多個版本JDK，本文主要介紹了Mac安裝多個JDK并實現(xiàn)動態(tài)切換，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
- jdk1.5 版本新增了JUC并發(fā)編程包,極大的簡化了傳統(tǒng)的多線程開發(fā),下面這篇文章主要介紹了Java線程池的四種拒絕策略的相關(guān)資料,文中通過實例代碼介紹的非常詳細，需要的朋友可以參考下2022-04-04
-
Java編程實現(xiàn)基于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索完整代碼
這篇文章主要介紹了Java編程實現(xiàn)基于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索完整代碼，具有一定借鑒價值，需要的朋友可以了解下。2017-12-12 -
springMVC在restful風(fēng)格的性能優(yōu)化方案
這篇文章主要介紹了springMVC在restful風(fēng)格的性能優(yōu)化方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08