欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

java面試題之?dāng)?shù)組中的逆序?qū)?/h1>

題目：在數(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)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(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ù)組分解稱兩個(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> <p> 網(wǎng)站欄目：<a href=java面試題之?dāng)?shù)組中的逆序?qū)?/a>
分享地址：http://chinadenli.net/article6/gjedog.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、做網(wǎng)站、微信小程序、網(wǎng)站建設(shè)、營(yíng)銷型網(wǎng)站建設(shè)、商城網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

搜索引擎優(yōu)化