算法入門篇二 認識O(NlogN)的排序

遞歸

例子引出

  • 使用遞歸的方法求出數組中的最大值（利用的是棧）
  • 求中點的方法改進
mid = (left + right) / 2  //但是如果left和right的數很大，相加會造成內容溢出
改進為 mid = left + (right - left) / 2  //(right - left)得到整個的長度，除以2之后，再加上左邊的點，就可以得到中點的位置
改進為 mid = left + (right - left) >> 1 //使用位運算，加快計算速度

代碼?

package com.example.demo.class01;public class Code08_GetMax {public static void main(String[] args) {int arr[] = {1,2,4,3,2,8,6};int c = 0;c = getMax(arr);System.out.println(c);}public static int getMax(int[] arr){if(arr == null || arr.length == 0){System.out.println("輸入數組不合理");}return process(arr,0,arr.length - 1);}public static int process(int[] arr,int L,int R){if(L == R){return arr[L];} //arr[L..R]只有一個數的時候，直接返回，base caseint mid = L + ((R - L)>>1);int leftMax = process(arr,L,mid);int rightMax = process(arr,mid+1,R);return Math.max(leftMax,rightMax);}
}
//8

master公示的使用

  • 用于分析遞歸，用于解決 子問題規模 是一致的問題
T(N) = a*T(N/b) + O(N^d)1,log(b,a) > d -> 復雜度為O(N^log(b,a))
2,log(b,a) = d -> 復雜度為O(N^d * logN)
3,log(b,a) < d -> 復雜度為O(N^d)

歸并排序

  • 整體就是一個簡單排序，左邊排好順序，右邊排好順序，使整體有序
  • 時間復雜度是O(N*logN)
  • 額外復雜度是O(N)

  • 代碼

package com.example.demo.class01;import java.util.Arrays;public class MergeSort {public static void mergeSort(int[] arr) {if (arr == null || arr.length < 2) {return;}process(arr, 0, arr.length - 1);}public static void process(int[] arr, int L, int R) {if (L == R) {return;}int mid = L + ((R - L) >> 1);process(arr, L, mid);process(arr, mid + 1, R);merge(arr, L, mid, R);}public static void merge(int[] arr, int L, int M, int R) {int[] help = new int[R - L + 1];int i = 0;int p1 = L;int p2 = M + 1;while (p1 <= M && p2 <= R) {help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= M) {help[i++] = arr[p1++];}while (p2 <= R) {help[i++] = arr[p2++];}for (i = 0; i < help.length; i++) {arr[L + i] = help[i];}}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 100;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);mergeSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);mergeSort(arr);printArray(arr);}}

小和問題

  • 定義：在一個數組中，每一個數比前數小的數進行累加，叫做這個數的小和。
  • 轉化為 （右邊大于我的個數 * 我本身大小）?累加和，這個數值和小和得到的數據一致

  • res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;p1指向左邊的數，p2指向右邊的數，r是右邊部分最右邊的邊界。r-p2 +1 得到比當前左邊元素大的個數 ，再乘以當前元素本身；將所有元素按照上述流程進行，最后就得到了小和

  • 例子：【1，3，4，2，5】，1左邊比1小的數：無；3左邊比3小的數：1；4左邊比4小的數：1，3；2左邊比2小的數：1；5左邊比5小的數：1，3，4，2；累加求和：16

使用歸并排序解決小和問題

  • 歸并排序，遇到相同的元素，先移動左側，是為了保證程序的穩定性；而這里先移動右側的元素，是為了確定比左側指針指向的元素大的右側區塊中的元素的個數
  • 小和問題出現在三個地方：左側區塊內排序；右側區塊內排序；左右側區塊合并

代碼

package class02;public class Code02_SmallSum {public static int smallSum(int[] arr) {if (arr == null || arr.length < 2) {return 0;}return process(arr, 0, arr.length - 1);}// arr[L..R]既要排好序，也要求小和public static int process(int[] arr, int l, int r) {if (l == r) {return 0;}int mid = l + ((r - l) >> 1);return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);}public static int merge(int[] arr, int L, int m, int r) {int[] help = new int[r - L + 1];int i = 0;int p1 = L;int p2 = m + 1;int res = 0;while (p1 <= m && p2 <= r) {res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= m) {help[i++] = arr[p1++];}while (p2 <= r) {help[i++] = arr[p2++];}for (i = 0; i < help.length; i++) {arr[L + i] = help[i];}return res;}// for testpublic static int comparator(int[] arr) {if (arr == null || arr.length < 2) {return 0;}int res = 0;for (int i = 1; i < arr.length; i++) {for (int j = 0; j < i; j++) {res += arr[j] < arr[i] ? arr[j] : 0;}}return res;}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 100;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);if (smallSum(arr1) != comparator(arr2)) {succeed = false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");}}
  • 類似于逆序對問題：如果左邊的數比右邊的數大，則二者構成一個逆序對，原理類似
  • res += arr[p1] > arr[p2] ? (m - p1 +1) : 0;

荷蘭國旗問題

  • 快速排序?
  • 給定數組arr和數num，將小于等于num的數放在數組的左邊，大于num的數放在數組的右邊，要求時間復雜度為O(N),空間復雜度為O(1);不要求內部有序

  • 將數組分為三個部分，以num為界限，分為小于等于區、大于區和待定區。指針指向數組的第一個元素，判定指針指向的元素是否小于等于num，如果成立當前數和小于等于區的下一個數交換，然后小于等于區向右移動，指針也向右移動
  • 如果指針指向的元素大于num，那么指針直接跳過該元素，向右移動。
package class02;public class Code05_NetherlandsFlag {public static int[] partition(int[] arr, int l, int r, int p) {int less = l - 1;int more = r + 1;while (l < more) {if (arr[l] < p) {swap(arr, ++less, l++);} else if (arr[l] > p) {swap(arr, --more, l);} else {l++;}}return new int[] { less + 1, more - 1 };}// for testpublic static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}// for testpublic static int[] generateArray() {int[] arr = new int[10];for (int i = 0; i < arr.length; i++) {arr[i] = (int) (Math.random() * 3);}return arr;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int[] test = generateArray();printArray(test);int[] res = partition(test, 0, test.length - 1, 1);printArray(test);System.out.println(res[0]);System.out.println(res[1]);}
}

第二個問題

  • 荷蘭國旗問題：給定數組arr和數num，將小于等于num的數放在數組的左邊，等于num的數放在數組的中間，大于num的數放在數組的右邊，要求時間復雜度為O(N),空間復雜度為O(1)

  • 將數組分為三個部分，小于區、中間區和大于區。
  • 首先用指針指向數組的第一個元素，如果當前指向的數小于num，則小于區下一個元素和當前數值側面交換，小于區域向右邊擴，指針向右邊移動
  • 如果當前指針指向的元素和num相等，那么指針直接跳過，移動到下一個位置
  • 如果當前指針指向的元素大于num，那么大于區的前一個元素和當前指針指向的元素交換，大于區域向左邊擴展，但是當前指針不可以移動位置，因為，交換了元素，不知道這個交換元素和num的大小
package class02;import java.util.Arrays;public class Code06_QuickSort {public static void quickSort(int[] arr) {if (arr == null || arr.length < 2) {return;}quickSort(arr, 0, arr.length - 1);}public static void quickSort(int[] arr, int l, int r) {if (l < r) {swap(arr, l + (int) (Math.random() * (r - l + 1)), r);int[] p = partition(arr, l, r);quickSort(arr, l, p[0] - 1);quickSort(arr, p[1] + 1, r);}}public static int[] partition(int[] arr, int l, int r) {int less = l - 1;int more = r;while (l < more) {if (arr[l] < arr[r]) {swap(arr, ++less, l++);} else if (arr[l] > arr[r]) {swap(arr, --more, l);} else {l++;}}swap(arr, more, r);return new int[] { less + 1, more };}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {//l到r隨機選一個數做等概率劃分 ，最差情況發生概率下降int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 100;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);quickSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);quickSort(arr);printArray(arr);}}
  • 快排的時間復雜度是 o(N*logN)

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/447227.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/447227.shtml
英文地址，請注明出處：http://en.pswp.cn/news/447227.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

算法入門篇三 詳解桶排序和整理排序知識 堆的相關操作 補充 不完整

算法入門篇三 詳解桶排序和整理排序知識 堆的相關操作 補充 不完整

歸并排序不使用遞歸 使用一個變量&#xff0c;使其按照1、2、4、8遞增&#xff0c;控制左右兩邊1個元素、2個元素、4個元素等元素的合并 完全二叉樹 完全二叉樹 要不全是滿的&#xff0c;要不葉子節點出現在最后一層&#xff0c;只要出現了葉子節點&#xff0c;后面的都是葉子…
閱讀更多...
C++著名程序庫

C++著名程序庫

1、C各大有名庫的介紹——C標準庫標準庫中提供了C程序的基本設施。雖然C標準庫隨著C標準折騰了許多年&#xff0c;直到標準的出臺才正式定型&#xff0c;但是在標準庫的實現上卻很令人欣慰得看到多種實現&#xff0c;并且已被實踐證明為有工業級別強度的佳作。 1.1、Dinkumware…
閱讀更多...
2023年12月24日學習總結

2023年12月24日學習總結

今日to do list&#xff1a; 做kaggle上面的流量預測項目?? 學習時不刷手機&#x1f921; okkkkkkkkkkkkkk 開始&#x1f44d;&#x1f34e; 0、我在干什么&#xff1f; 我在預測一個名字叫做elborn基站的下行鏈路流量&#xff0c;用過去29天的數據預測未來10天的數據 1、…
閱讀更多...
Mac/Linux系統連接遠端服務器以及相同IP地址的服務器賬號密碼重置，ssh失敗問題

Mac/Linux系統連接遠端服務器以及相同IP地址的服務器賬號密碼重置，ssh失敗問題

連接遠端服務器 ssh 賬號IP地址 輸入完成之后會提示輸入密碼&#xff0c;密碼輸入正確后&#xff0c;就可以連接成功了 重置ssh密鑰 如果連接的服務器除了IP地址沒有改變&#xff0c;其余的賬號、密碼、系統等都變了的話&#xff0c;因為曾經連接過的歷史數據會保存到本地&a…
閱讀更多...
內存泄漏快速定位方法

內存泄漏快速定位方法

主要方法&#xff1a;利用系統帶的函數&#xff1a;EnableMemLeakCheck() 和函數重載&#xff0c;能快速準備的定位到內存泄漏的地方&#xff0c;方法簡單且實用&#xff0c;值得借用。 #include <crtdbg.h> #ifdef_DEBUG //重載一下new函數&#xff0c;這樣能得到使…
閱讀更多...
Linux操作系統監視NVIDIA的GPU使用情況

Linux操作系統監視NVIDIA的GPU使用情況

對于GPU相關參數介紹 使用命令周期性查看GPU運行情況最常用的參數是 -n&#xff0c; 后面指定是每多少秒來執行一次命令。監視顯存&#xff1a;設置為每 1s 顯示一次顯存的情況&#xff1a;使用命令ctrlz退出 watch -n 1 nvidia-smi 參數介紹 Fan&#xff1a;顯示風扇轉速&am…
閱讀更多...
一個軟件工程師的職業規劃

一個軟件工程師的職業規劃

[1]好好規劃自己的路&#xff0c;不要跟著感覺走&#xff01;根據個人的理想決策安排&#xff0c;絕大部分人并不指望成為什么院士或教授&#xff0c;而是希望活得滋潤一些&#xff0c;爽一些。那么&#xff0c;就需要慎重安排自己的軌跡。從哪個行業入手&#xff0c;逐漸對該行…
閱讀更多...
算法入門篇四 桶排序

算法入門篇四 桶排序

桶排序 計數排序&#xff08;基于統計&#xff09; 要求數據是有限的&#xff0c;和數據狀況有關&#xff0c;比如對于200個人統計他們的年齡分布&#xff0c;這個時候需要申請200個桶&#xff0c;因此對于輸入數據的規模有限制&#xff0c;如果輸入規模是不定的&#xff0c;…
閱讀更多...
RTP概述

RTP概述

1.1. RTP是什么 RTP全名是Real-time Transport Protocol&#xff08;實時傳輸協議&#xff09;。它是IETF提出的一個標準&#xff0c;對應的RFC文檔為RFC3550&#xff08;RFC1889為其過期版本&#xff09;。RFC3550不僅定義了RTP&#xff0c;而且定義了配套的相關協議RTCP&…
閱讀更多...
Java需要注意的一些小細節

Java需要注意的一些小細節

更加精確的鎖定時間 判定納秒維度的時間 //使用System.nanoTime(); //例子 long start System.nanoTime(); long end System.nanoTime(); System.out.println(start); System.out.println(end);
閱讀更多...
live555的安裝 RTSP點播消息流程實例（客戶端：VLC， RTSP服務器：LIVE555 Media Server)

live555的安裝 RTSP點播消息流程實例（客戶端：VLC， RTSP服務器：LIVE555 Media Server)

live555是一個開源的軟件&#xff0c;主要用來生成rtsp,rtp和sip服務器和客戶端的軟件。前幾天需要看一下vlc中的rtsp的功能&#xff0c;在vlc中rtp和rtsp的功能都是使用live555中的函數來生成的。該開源軟件的編譯&#xff0c;可以使用vc,mingw和cygwin等軟件。我安裝的時候使…
閱讀更多...
算法入門篇五 鏈表

算法入門篇五 鏈表

牛客網 算法入門篇 判斷一個鏈表是否為回文結構 給定一個單鏈表的頭節點head&#xff0c;請判斷這個鏈表是否為回文結構1->2->1&#xff0c;返回為True;1->2->3為False 思路&#xff1a; 1&#xff0c;遍歷鏈表&#xff0c;將所有元素壓入棧中&#xff0c;然后再…
閱讀更多...
實時流媒體編程基于Linux環境開發

實時流媒體編程基于Linux環境開發

一、流媒體簡介 隨著Internet的日益普及&#xff0c;在網絡上傳輸的數據已經不再局限于文字和圖形&#xff0c;而是逐漸向聲音和視頻等多媒體格式過渡。目前在網絡上傳輸音頻/視頻&#xff08;Audio/Video&#xff0c;簡稱A/V&#xff09;等多媒體文件時&#xff0c;基本上只有…
閱讀更多...
算法入門篇六 二叉樹

算法入門篇六 二叉樹

牛客網 算法入門篇 左程云老師 個人復習&#xff0c;如果侵全&#xff0c;設為私密 二叉樹遍歷&#xff08;遞歸&#xff09; 先序遍歷&#xff08;中&#xff0c;左&#xff0c;右&#xff09; 中序遍歷&#xff08;左&#xff0c;中&#xff0c;右&#xff09; 后序遍歷&a…
閱讀更多...
VLC詳細的使用說明以及配置說明綜合示范實例精通VLC開發

VLC詳細的使用說明以及配置說明綜合示范實例精通VLC開發

vlc的全名是Video LanClient&#xff0c;是一個開源的、跨平臺的視頻播放器。VLC支持大量的音視頻傳輸、封裝和編碼格式&#xff0c;完整的功能特性列表可以在這里獲得http://www.videolan.org/vlc/features.html&#xff0c;下面給出一個簡要的不完整的列表&#xff1a;操作系…
閱讀更多...
算法入門篇七 前綴樹

算法入門篇七 前綴樹

牛客網 左程云老師的算法入門課 找二叉樹的節點的后繼節點 原則 如果節點有右子樹&#xff0c;那么后繼節點就是右子樹的最左邊的第一個節點如果節點沒有右子樹&#xff0c;如果節點是父節點的右孩子&#xff0c;就繼續往上找&#xff0c;直到找到一個父節點是沿途節點的父節…
閱讀更多...
VLC視頻播放器原理詳細分析含TS流格式分析

VLC視頻播放器原理詳細分析含TS流格式分析

vlc是一個功能強大的玩意&#xff0c;能做很多有意思的事情。最簡單的&#xff0c;從界面打開一個文件播放&#xff0c;也可以在命令行下使用&#xff0c;如C:\Program Files\VideoLAN\VLC>vlc.exe test.ts獲取內置的幫助&#xff0c;會寫到vlc-help.txtC:\Program Files\Vi…
閱讀更多...
算法入門篇八 貪心算法

算法入門篇八 貪心算法

牛客網 左程云老師的算法入門課 貪心算法 貪心算法的解題步驟 例子 題目要求 解題策略 按照結束時間早的會議先安排&#xff0c;比如先安排【2&#xff0c;4】&#xff0c;當4結束了&#xff0c;所有開始時間小于4的全部淘汰&#xff0c;【1&#xff0c;7】、【3&#xff…
閱讀更多...
算法入門篇九 暴力遞歸

算法入門篇九 暴力遞歸

牛客網 左程云老師的算法入門課 暴力遞歸 原則 漢諾塔問題 問題 打印n層漢諾塔從左邊移動到最右邊的過程 思想 一共六個過程&#xff0c;左到右、左到中&#xff0c;中到左&#xff0c;中到右&#xff0c;右到左&#xff0c;右到中&#xff0c;互相嵌套使用 左到右 將1…
閱讀更多...
rtsp和sdp

rtsp和sdp

RTSP 是由Realnetwork 和Netscape共同提出的如何有效地在IP網絡上傳輸流媒體數據的應用層協議 。 實時流協議&#xff08;RTSP&#xff09;建立并控制一個或幾個時間同步的連續流媒體&#xff0c;如音頻和視頻。盡管連續媒體流與控制流交叉是可能的&#xff0c;RTSP本身并不發…
閱讀更多...
最新文章

Copyright @ 2022~2023