java面試題之?dāng)?shù)組中的逆序?qū)?/h1>
更新時(shí)間：2019年03月05日 08:17:52 作者：水的化合物的專欄
這篇文章主要為大家詳細(xì)介紹了java面試題之?dāng)?shù)組中的逆序?qū)?，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
題目：在數(shù)組中的兩個(gè)數(shù)字如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)Α］斎胍粋€(gè)數(shù)組，求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)
例如在數(shù)組｛7，5，6，4｝中，一共存在5對逆序?qū)?，分別是｛7，6｝，｛7，5｝，｛7，4｝，｛6，4｝，｛5，4｝。
看到這個(gè)題目，我們的第一反應(yīng)就是順序掃描整個(gè)數(shù)組。每掃描到一個(gè)數(shù)組的時(shí)候，逐個(gè)比較該數(shù)字和它后面的數(shù)字的大小。如果后面的數(shù)字比它小，則這兩個(gè)數(shù)字就組成一個(gè)逆序?qū)?。假設(shè)數(shù)組中含有n個(gè)數(shù)字。由于每個(gè)數(shù)字都要和O(n）個(gè)數(shù)字做比較，因此這個(gè)算法的時(shí)間復(fù)雜度為O(n2)。我們嘗試找找更快的算法。
我們以數(shù)組｛7，5，6，4｝為例來分析統(tǒng)計(jì)逆序?qū)Φ倪^程，每次掃描到一個(gè)數(shù)字的時(shí)候，我們不能拿它和后面的每一個(gè)數(shù)字做比較，否則時(shí)間復(fù)雜度就是O(n2)因此我們可以考慮先比較兩個(gè)相鄰的數(shù)字。
如下圖所示，我們先把數(shù)組分解稱兩個(gè)長度為2的子數(shù)組，再把這兩個(gè)子數(shù)組分別茶城兩個(gè)長度為1的子數(shù)組。接下來一邊合并相鄰的子數(shù)組，一邊統(tǒng)計(jì)逆序?qū)Φ臄?shù)目。在第一對長度為1的子數(shù)組｛7｝，｛5｝中7大于5，因此｛7，5｝組成一個(gè)逆序?qū)ΑＭ瑯釉诘诙﹂L度為1的子數(shù)組｛6｝，｛4｝中也有逆序?qū)Γ?，4｝。由于我們已經(jīng)統(tǒng)計(jì)了這兩隊(duì)子數(shù)組內(nèi)部逆序?qū)?，因此需要把這兩對子數(shù)組排序，以免在以后的統(tǒng)計(jì)過程中再重復(fù)統(tǒng)計(jì)。
接下來我們統(tǒng)計(jì)兩個(gè)長度為2的子數(shù)組之間的逆序?qū)Α?/p>
我們先用兩個(gè)指針分別指向兩個(gè)子數(shù)組的末尾，并每次比較兩個(gè)指針指向的數(shù)字。如果第一個(gè)子數(shù)組中的數(shù)字大于第二個(gè)子數(shù)組中的數(shù)字，則構(gòu)成逆序?qū)?，并且逆序?qū)Φ臄?shù)目等于第二個(gè)子數(shù)組中的剩余數(shù)字的個(gè)數(shù)。如果第一個(gè)數(shù)組中的數(shù)字小于或等于第二個(gè)數(shù)組中的數(shù)字，則不構(gòu)成逆序?qū)?。每一次比較的時(shí)候，我們都把較大的數(shù)字從后往前復(fù)制到一個(gè)輔助數(shù)組中去，確保輔助數(shù)組中的數(shù)字是遞增排序的。在把較大的數(shù)字復(fù)制到數(shù)組之后，把對應(yīng)的指針向前移動(dòng)一位，接著來進(jìn)行下一輪的比較。
經(jīng)過前面詳細(xì)的討論，我們可以總結(jié)出統(tǒng)計(jì)逆序?qū)Φ倪^程：先把數(shù)組分隔成子數(shù)組，先統(tǒng)計(jì)出子數(shù)組內(nèi)部的逆序?qū)Φ臄?shù)目，然后再統(tǒng)計(jì)出兩個(gè)相鄰子數(shù)組之間的逆序?qū)Φ臄?shù)目。在統(tǒng)計(jì)逆序?qū)Φ倪^程中，還需要對數(shù)組進(jìn)行排序。如果對排序算法很熟悉，我們不難發(fā)現(xiàn)這個(gè)排序的過程就是歸并排序。
static int count = 0;
// 將有二個(gè)有序數(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++];
// 因?yàn)槿绻鸻[i]此時(shí)比右數(shù)組的當(dāng)前元素a[j]大，
// 那么左數(shù)組中a[i]后面的元素就都比a[j]大
// 【因?yàn)閿?shù)組此時(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); // 再將二個(gè)有序數(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的JSON轉(zhuǎn)換類庫GSON的基礎(chǔ)使用教程
GSON是谷歌開源的一款Java對象與JSON對象互相轉(zhuǎn)換的類庫,Java的JSON轉(zhuǎn)換類庫GSON的基礎(chǔ)使用教程,需要的朋友可以參考下 2016-06-06
-
這篇文章主要給大家介紹了關(guān)于Java?17新特性詳細(xì)講解與代碼實(shí)例的相關(guān)資料,Java 17是2021年9月發(fā)布的最新版本,其中包含了很多新特性和改進(jìn),這些新特性和改進(jìn)將進(jìn)一步提高 Java 語言的性能和可用性,需要的朋友可以參考下 2023-09-09
-
Springmvc RequestMapping請求實(shí)現(xiàn)方法解析
這篇文章主要介紹了Springmvc RequestMapping請求實(shí)現(xiàn)方法解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下 2020-09-09
-
Springmvc異常處理器及攔截器實(shí)現(xiàn)代碼
這篇文章主要介紹了Springmvc異常處理器及攔截器實(shí)現(xiàn)代碼,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下 2020-10-10
-
這篇文章主要介紹了使用Feign調(diào)用第三方http接口，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教 2022-03-03
-
自定義SpringBoot的白標(biāo)錯(cuò)誤頁面的操作方法
Spring Boot的白標(biāo)錯(cuò)誤頁面是在應(yīng)用程序出現(xiàn)錯(cuò)誤時(shí)(如404或500 HTTP狀態(tài)碼)自動(dòng)生成的默認(rèn)錯(cuò)誤頁面,下面小編給大家分享如何自定義SpringBoot的白標(biāo)錯(cuò)誤頁面,感興趣的朋友跟隨小編一起看看吧 2024-06-06
-
所謂的配置文件問題，是指我們在開發(fā)時(shí)，經(jīng)常需要讀取和修改一些配置信息，比如數(shù)據(jù)庫、消息隊(duì)列、Nginx、Web服務(wù)器等的配置，為了便于修改這些信息，我們可以采用Properties配置類，本文給大家講一下Properties配置類是怎么回事，以及怎么使用 2023-06-06
-
這篇文章主要介紹了一個(gè)java播放聲音類和一個(gè)java播放聲音的應(yīng)用程序，應(yīng)用程序可以單次播放聲音、循環(huán)播放聲音,需要的朋友可以參考下 2014-03-03
-
mybatis和ibatis總體來講都差不多的。下面小編給大家探討下mybatis中#{}和${}的區(qū)別，感興趣的朋友一起學(xué)習(xí)吧 2016-08-08
-
這篇文章主要介紹了使用jpa原生sql@Query操作增刪改查，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教 2021-06-06
最新評論
題目：在數(shù)組中的兩個(gè)數(shù)字如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)Α］斎胍粋€(gè)數(shù)組，求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)
例如在數(shù)組｛7，5，6，4｝中，一共存在5對逆序?qū)?，分別是｛7，6｝，｛7，5｝，｛7，4｝，｛6，4｝，｛5，4｝。
看到這個(gè)題目，我們的第一反應(yīng)就是順序掃描整個(gè)數(shù)組。每掃描到一個(gè)數(shù)組的時(shí)候，逐個(gè)比較該數(shù)字和它后面的數(shù)字的大小。如果后面的數(shù)字比它小，則這兩個(gè)數(shù)字就組成一個(gè)逆序?qū)?。假設(shè)數(shù)組中含有n個(gè)數(shù)字。由于每個(gè)數(shù)字都要和O(n）個(gè)數(shù)字做比較，因此這個(gè)算法的時(shí)間復(fù)雜度為O(n2)。我們嘗試找找更快的算法。
我們以數(shù)組｛7，5，6，4｝為例來分析統(tǒng)計(jì)逆序?qū)Φ倪^程，每次掃描到一個(gè)數(shù)字的時(shí)候，我們不能拿它和后面的每一個(gè)數(shù)字做比較，否則時(shí)間復(fù)雜度就是O(n2)因此我們可以考慮先比較兩個(gè)相鄰的數(shù)字。
如下圖所示，我們先把數(shù)組分解稱兩個(gè)長度為2的子數(shù)組，再把這兩個(gè)子數(shù)組分別茶城兩個(gè)長度為1的子數(shù)組。接下來一邊合并相鄰的子數(shù)組，一邊統(tǒng)計(jì)逆序?qū)Φ臄?shù)目。在第一對長度為1的子數(shù)組｛7｝，｛5｝中7大于5，因此｛7，5｝組成一個(gè)逆序?qū)ΑＭ瑯釉诘诙﹂L度為1的子數(shù)組｛6｝，｛4｝中也有逆序?qū)Γ?，4｝。由于我們已經(jīng)統(tǒng)計(jì)了這兩隊(duì)子數(shù)組內(nèi)部逆序?qū)?，因此需要把這兩對子數(shù)組排序，以免在以后的統(tǒng)計(jì)過程中再重復(fù)統(tǒng)計(jì)。
接下來我們統(tǒng)計(jì)兩個(gè)長度為2的子數(shù)組之間的逆序?qū)Α?/p>
我們先用兩個(gè)指針分別指向兩個(gè)子數(shù)組的末尾，并每次比較兩個(gè)指針指向的數(shù)字。如果第一個(gè)子數(shù)組中的數(shù)字大于第二個(gè)子數(shù)組中的數(shù)字，則構(gòu)成逆序?qū)?，并且逆序?qū)Φ臄?shù)目等于第二個(gè)子數(shù)組中的剩余數(shù)字的個(gè)數(shù)。如果第一個(gè)數(shù)組中的數(shù)字小于或等于第二個(gè)數(shù)組中的數(shù)字，則不構(gòu)成逆序?qū)?。每一次比較的時(shí)候，我們都把較大的數(shù)字從后往前復(fù)制到一個(gè)輔助數(shù)組中去，確保輔助數(shù)組中的數(shù)字是遞增排序的。在把較大的數(shù)字復(fù)制到數(shù)組之后，把對應(yīng)的指針向前移動(dòng)一位，接著來進(jìn)行下一輪的比較。
經(jīng)過前面詳細(xì)的討論，我們可以總結(jié)出統(tǒng)計(jì)逆序?qū)Φ倪^程：先把數(shù)組分隔成子數(shù)組，先統(tǒng)計(jì)出子數(shù)組內(nèi)部的逆序?qū)Φ臄?shù)目，然后再統(tǒng)計(jì)出兩個(gè)相鄰子數(shù)組之間的逆序?qū)Φ臄?shù)目。在統(tǒng)計(jì)逆序?qū)Φ倪^程中，還需要對數(shù)組進(jìn)行排序。如果對排序算法很熟悉，我們不難發(fā)現(xiàn)這個(gè)排序的過程就是歸并排序。
static int count = 0;
// 將有二個(gè)有序數(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++];
// 因?yàn)槿绻鸻[i]此時(shí)比右數(shù)組的當(dāng)前元素a[j]大，
// 那么左數(shù)組中a[i]后面的元素就都比a[j]大
// 【因?yàn)閿?shù)組此時(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); // 再將二個(gè)有序數(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的JSON轉(zhuǎn)換類庫GSON的基礎(chǔ)使用教程
GSON是谷歌開源的一款Java對象與JSON對象互相轉(zhuǎn)換的類庫,Java的JSON轉(zhuǎn)換類庫GSON的基礎(chǔ)使用教程,需要的朋友可以參考下2016-06-06 - 這篇文章主要給大家介紹了關(guān)于Java?17新特性詳細(xì)講解與代碼實(shí)例的相關(guān)資料,Java 17是2021年9月發(fā)布的最新版本,其中包含了很多新特性和改進(jìn),這些新特性和改進(jìn)將進(jìn)一步提高 Java 語言的性能和可用性,需要的朋友可以參考下2023-09-09
-
Springmvc RequestMapping請求實(shí)現(xiàn)方法解析
這篇文章主要介紹了Springmvc RequestMapping請求實(shí)現(xiàn)方法解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-09-09 -
Springmvc異常處理器及攔截器實(shí)現(xiàn)代碼
這篇文章主要介紹了Springmvc異常處理器及攔截器實(shí)現(xiàn)代碼,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-10-10 - 這篇文章主要介紹了使用Feign調(diào)用第三方http接口，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-03-03
-
自定義SpringBoot的白標(biāo)錯(cuò)誤頁面的操作方法
Spring Boot的白標(biāo)錯(cuò)誤頁面是在應(yīng)用程序出現(xiàn)錯(cuò)誤時(shí)(如404或500 HTTP狀態(tài)碼)自動(dòng)生成的默認(rèn)錯(cuò)誤頁面,下面小編給大家分享如何自定義SpringBoot的白標(biāo)錯(cuò)誤頁面,感興趣的朋友跟隨小編一起看看吧2024-06-06 - 所謂的配置文件問題，是指我們在開發(fā)時(shí)，經(jīng)常需要讀取和修改一些配置信息，比如數(shù)據(jù)庫、消息隊(duì)列、Nginx、Web服務(wù)器等的配置，為了便于修改這些信息，我們可以采用Properties配置類，本文給大家講一下Properties配置類是怎么回事，以及怎么使用2023-06-06
- 這篇文章主要介紹了一個(gè)java播放聲音類和一個(gè)java播放聲音的應(yīng)用程序，應(yīng)用程序可以單次播放聲音、循環(huán)播放聲音,需要的朋友可以參考下2014-03-03
- mybatis和ibatis總體來講都差不多的。下面小編給大家探討下mybatis中#{}和${}的區(qū)別，感興趣的朋友一起學(xué)習(xí)吧2016-08-08
- 這篇文章主要介紹了使用jpa原生sql@Query操作增刪改查，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-06-06