使用歸併排序演算法編寫的C/C++程式來計算數組中的逆序對數?
對給定數組進行排序時發生的反轉計數稱為反轉計數。逆問題是一個經典問題,可以使用歸併排序演算法來解決。在此問題 v 中,我們將計算其左側大於它的所有元素,並將計數新增至輸出。這個邏輯是在合併排序的合併函數中完成的。
為了更好地理解這個主題,讓我們舉個例子。讓我們考慮合併過程中涉及的兩個子陣列-
##
Input: arr[] = { 1, 9, 6, 4, 5} Output: Inversion count is 5
說明
陣列的反轉次數
給定一個陣列,找出它的反轉次數。如果 (i < j) 和 (A[i] > A[j]) 則 (i, j) 對稱為陣列 A 的反轉。我們需要對arr 中所有此類對進行計數
< p>例如,數組中有5個反轉
(9,6), (9,4), (9,5), (6,4), (6,5)
#1.互相比較元素的值。
2.如果較低索引處的值較高,則增加計數器。
3.顯示結果。
範例
#include <stdio.h> int Merge(int arr[], int aux[], int low, int mid, int high) { int k = low, i = low, j = mid + 1; int inversionCount = 0; while (i <= mid && j <= high) { if (arr[i] <= arr[j]) { aux[k++] = arr[i++]; } else { aux[k++] = arr[j++]; inversionCount += (mid - i + 1); // NOTE } } while (i <= mid) aux[k++] = arr[i++]; for (int i = low; i <= high; i++) arr[i] = aux[i]; return inversionCount; } int MergeSort(int arr[], int aux[], int low, int high) { if (high == low) // if run size == 1 return 0; int mid = (low + ((high - low) >> 1)); int inversionCount = 0; inversionCount += MergeSort(arr, aux, low, mid); inversionCount += MergeSort(arr, aux, mid + 1, high); inversionCount += Merge(arr, aux, low, mid, high); return inversionCount; } int main() { int arr[] = { 1, 9, 6, 4, 5 }; int N = 5; int aux[N]; for (int i = 0; i < N; i++) aux[i] = arr[i]; printf("Inversion count is %d", MergeSort(arr, aux, 0, N - 1)); return 0; }
以上是使用歸併排序演算法編寫的C/C++程式來計算數組中的逆序對數?的詳細內容。更多資訊請關注PHP中文網其他相關文章!

熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

使用foreach循環移除PHP數組中重複元素的方法如下:遍歷數組,若元素已存在且當前位置不是第一個出現的位置,則刪除它。舉例而言,若資料庫查詢結果有重複記錄,可使用此方法移除,得到不含重複記錄的結果。

PHP數組鍵值翻轉方法效能比較顯示:array_flip()函數在大型數組(超過100萬個元素)下比for迴圈效能更優,耗時更短。手動翻轉鍵值的for迴圈方法耗時相對較長。

PHP中深度複製數組的方法包括:使用json_decode和json_encode進行JSON編碼和解碼。使用array_map和clone進行深度複製鍵和值的副本。使用serialize和unserialize進行序列化和反序列化。

多維數組排序可分為單列排序和嵌套排序。單列排序可使用array_multisort()函數依列排序;巢狀排序需要遞歸函數遍歷陣列並排序。實戰案例包括按產品名稱排序和按銷售量和價格複合排序。

PHP的array_group_by函數可依鍵或閉包函數將陣列中的元素分組,傳回關聯數組,其中鍵為組名,值是屬於該組的元素數組。

在PHP中執行陣列深度複製的最佳實踐是:使用json_decode(json_encode($arr))將陣列轉換為JSON字串,然後再轉換回陣列。使用unserialize(serialize($arr))將陣列序列化為字串,然後將其反序列化為新陣列。使用RecursiveIteratorIterator迭代器對多維數組進行遞歸遍歷。

PHP陣列去重演算法的複雜度:array_unique():O(n)array_flip()+array_keys():O(n)foreach迴圈:O(n^2)

PHP的array_group()函數可用來按指定鍵對陣列進行分組,以尋找重複元素。函數透過以下步驟運作:使用key_callback指定分組鍵。可選地使用value_callback確定分組值。對分組元素進行計數並識別重複項。因此,array_group()函數對於尋找和處理重複元素非常有用。
