題目：在數(shù)組中的兩個(gè)數(shù)字如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)?。輸入一個(gè)數(shù)組，求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)
目前創(chuàng)新互聯(lián)已為近1000家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)頁(yè)空間、網(wǎng)站托管、服務(wù)器租用、企業(yè)網(wǎng)站設(shè)計(jì)、荊州網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶(hù)導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶(hù)和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。
例如在數(shù)組｛7，5，6，4｝中，一共存在5對(duì)逆序?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ū)Α＜僭O(shè)數(shù)組中含有n個(gè)數(shù)字。由于每個(gè)數(shù)字都要和O(n）個(gè)數(shù)字做比較，因此這個(gè)算法的時(shí)間復(fù)雜度為O(n2)。我們嘗試找找更快的算法。
我們以數(shù)組｛7，5，6，4｝為例來(lái)分析統(tǒng)計(jì)逆序?qū)Φ倪^(guò)程，每次掃描到一個(gè)數(shù)字的時(shí)候，我們不能拿它和后面的每一個(gè)數(shù)字做比較，否則時(shí)間復(fù)雜度就是O(n2)因此我們可以考慮先比較兩個(gè)相鄰的數(shù)字。
如下圖所示，我們先把數(shù)組分解稱(chēng)兩個(gè)長(zhǎng)度為2的子數(shù)組，再把這兩個(gè)子數(shù)組分別茶城兩個(gè)長(zhǎng)度為1的子數(shù)組。接下來(lái)一邊合并相鄰的子數(shù)組，一邊統(tǒng)計(jì)逆序?qū)Φ臄?shù)目。在第一對(duì)長(zhǎng)度為1的子數(shù)組｛7｝，｛5｝中7大于5，因此｛7，5｝組成一個(gè)逆序?qū)ΑＭ瑯釉诘诙?duì)長(zhǎng)度為1的子數(shù)組｛6｝，｛4｝中也有逆序?qū)Γ?，4｝。由于我們已經(jīng)統(tǒng)計(jì)了這兩隊(duì)子數(shù)組內(nèi)部逆序?qū)?，因此需要把這兩對(duì)子數(shù)組排序，以免在以后的統(tǒng)計(jì)過(guò)程中再重復(fù)統(tǒng)計(jì)。
![java面試題之?dāng)?shù)組中的逆序?qū)?></p><p>接下來(lái)我們統(tǒng)計(jì)兩個(gè)長(zhǎng)度為2的子數(shù)組之間的逆序?qū)Α?/p><p>我們先用兩個(gè)指針?lè)謩e指向兩個(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ù)組之后，把對(duì)應(yīng)的指針向前移動(dòng)一位，接著來(lái)進(jìn)行下一輪的比較。</p><p>經(jīng)過(guò)前面詳細(xì)的討論，我們可以總結(jié)出統(tǒng)計(jì)逆序?qū)Φ倪^(guò)程：先把數(shù)組分隔成子數(shù)組，先統(tǒng)計(jì)出子數(shù)組內(nèi)部的逆序?qū)Φ臄?shù)目，然后再統(tǒng)計(jì)出兩個(gè)相鄰子數(shù)組之間的逆序?qū)Φ臄?shù)目。在統(tǒng)計(jì)逆序?qū)Φ倪^(guò)程中，還需要對(duì)數(shù)組進(jìn)行排序。如果對(duì)排序算法很熟悉，我們不難發(fā)現(xiàn)這個(gè)排序的過(guò)程就是歸并排序。</p><div><pre> 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);
}
</pre></div><p>以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持創(chuàng)新互聯(lián)。</p>
<br>
分享題目：java面試題之?dāng)?shù)組中的逆序?qū)? <br>
網(wǎng)頁(yè)URL：<a href=](/upload/otherpic55/98870.jpg)
http://weahome.cn/article/gjedog.html
重慶分公司
重慶分公司
