柚子快報激活碼778899分享：【算法專場】分治（上）
柚子快報激活碼778899分享：【算法專場】分治（上）
目錄
前言
什么是分治？
75. 顏色分類
算法分析
算法步驟
算法代碼
912. 排序數(shù)組 - 力扣（LeetCode）
算法分析
算法步驟
算法代碼
215. 數(shù)組中的第K個最大元素 - 力扣（LeetCode）
算法分析
算法步驟
?編輯?
算法代碼
LCR 159. 庫存管理 III - 力扣（LeetCode）?
算法分析
算法步驟
算法代碼
前言
在前面，我們學習了八大排序，那么其中的快速排序和歸并排序都用到了分治的思想。在算法中，有時候我們也需要利用分治的思想來解決一些算法問題。本篇我們主要講解快速排序。
什么是分治？
分治算法是一種算法設計策略，將大問題轉(zhuǎn)化為小問題，再將小問題轉(zhuǎn)化為更小的問題，通過解決子問題來大問題。也就是說，把問題分解成若干個規(guī)模較小的問題，然后通過遞歸的方法來解決這些子問題，最后將子問題合并起來得到想要的結(jié)果。
步驟：
分解：將問題分解成若干個較小且獨立的子問題，一般是通過遞歸實現(xiàn)；解決：分解成小問題之后，在每個子問題中解決問題需求歸并：把問題解決完之后，將子問題進行合并。
接下來，我們就來通過一些練習來加深對分治思想的理解。
75. 顏色分類
算法分析
這道題的話就是要求我們將0、1、2這三個數(shù)依次從小排到大，那么對于這道題的話，其實我們有好幾種排序方法都可以解決這道題，甚至我們可以使用java中的Arrays.sort()方法都可以解決，但是這里是不允許的。我們這里可以使用分治的思想來解決這道題。
算法步驟
算法代碼
class Solution {
/**
* 交換數(shù)組中的兩個元素
*
* @param arr 數(shù)組
* @param left 左側(cè)元素的索引
* @param right 右側(cè)元素的索引
*/
public void swap(int[] arr, int left, int right) {
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
}
/**
* 對顏色進行排序，將0放到數(shù)組的左邊，2放到數(shù)組的右邊，1保持原位
*
* @param nums 需要排序的顏色數(shù)組，其中的顏色用0、1、2表示
*/
public void sortColors(int[] nums) {
int n = nums.length;
int i = 0, left = -1, right = n;
// 遍歷數(shù)組，根據(jù)元素的值進行交換，最終達到0在左邊，2在右邊的目的
while (i < right) {
if (nums[i] == 0) {
swap(nums, i++, ++left);
} else if (nums[i] == 2) {
swap(nums, i, --right);
} else {
i++;
}
}
}
}
時間復雜度為O(n),空間復雜度為O(1).?
912. 排序數(shù)組 - 力扣（LeetCode）
算法分析
對于這種排序的題目，其實我們有很多種排序的方法可以解決，但是我們這里只講如何使用分治的思想來解決這些排序題。?
算法步驟
對于這道題，我們可以采用分治的思想來解決，將數(shù)組劃分為n個子數(shù)組，并且在n個子數(shù)組中使用類似快排的步驟來進行排序。同時我們需要注意：快排在趨近有序的情況下的時間復雜度為O(n^2),所以我們可以采用優(yōu)化方法，如三數(shù)取中法，隨機取值方法，這里我們采用的是隨機取值法，使得算法的時間步驟度降為O(N*logN)
算法代碼
/**
* Solution 類用于提供一種基于快速排序的數(shù)組排序解決方案
*/
class Solution {
/**
* 對數(shù)組進行快速排序
*
* @param nums 待排序的整數(shù)數(shù)組
* @return 排序后的數(shù)組
*/
public int[] sortArray(int[] nums) {
qsort(nums, 0, nums.length - 1);
return nums;
}
/**
* 交換數(shù)組中兩個指定位置的元素
*
* @param nums 整數(shù)數(shù)組
* @param left 左側(cè)位置索引
* @param right 右側(cè)位置索引
*/
public void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
/**
* 使用快速排序算法對數(shù)組進行排序
*
* @param nums 待排序的整數(shù)數(shù)組
* @param left 排序開始的左邊界索引
* @param right 排序結(jié)束的右邊界索引
*/
public void qsort(int[] nums, int left, int right) {
if (left >= right) return;
int key = nums[new Random().nextInt(right - left + 1) + left];
int i = left, L = left - 1, R = right + 1;
while (i < R) {
if (nums[i] < key) swap(nums, ++L, i++);
else if (nums[i] == key) i++;
else swap(nums, i, --R);
}
qsort(nums, left, L);
qsort(nums, R, right);
}
}
215. 數(shù)組中的第K個最大元素 - 力扣（LeetCode）
算法分析
這道題其實就是TOP-K問題，我們可以使用優(yōu)先級隊列（堆）的方法來解決這個問題：首先我們可以創(chuàng)建一個小根堆，在這個小根堆中放入k個元素，接著遍歷剩余的n-k個元素，查看堆頂元素是不是小于數(shù)組中的元素，若小于則進行替換。當然，我們這里主要講分治思想，那么我們同樣是利用快排來解決這道題。
算法步驟
算法代碼
/**
* Solution類用于解決尋找數(shù)組中第k大的元素的問題
*/
class Solution {
/**
* 尋找數(shù)組中第k大的元素
*
* @param nums 輸入的整數(shù)數(shù)組
* @param k 指定的第k大元素
* @return 數(shù)組中第k大的元素
*/
public int findKthLargest(int[] nums, int k) {
// 調(diào)用快速排序相關函數(shù)來尋找第k大的元素
return qsort(nums, 0, nums.length - 1, k);
}
/**
* 快速排序算法的實現(xiàn)，用于尋找第k大的元素
*
* @param nums 輸入的整數(shù)數(shù)組
* @param l 排序區(qū)間的左邊界
* @param r 排序區(qū)間的右邊界
* @param k 指定的第k大元素
* @return 第k大的元素
*/
private int qsort(int[] nums, int l, int r, int k) {
// 如果左右指針相遇，直接返回該位置的元素
if(l == r) return nums[l];
// 隨機選擇一個基準值
int key = nums[new Random().nextInt(r - l + 1) + l];
int left = l - 1, right = r + 1, i = l;
// 分區(qū)過程，將數(shù)組分為三部分：小于基準值的、等于基準值的和大于基準值的
while(i < right) {
if(nums[i] < key) swap(nums, ++left, i++);
else if(nums[i] > key) swap(nums, i, --right);
else i++;
}
// 根據(jù)分區(qū)結(jié)果，決定下一步的查找范圍
int b = right - left - 1; // 等于基準值的區(qū)域大小
int c = r - right + 1; // 大于基準值的區(qū)域大小
if(c >= k) return qsort(nums, right, r, k); // 如果第k大在大于基準值的區(qū)域
else if(b + c >= k) return key; // 如果第k大在等于基準值的區(qū)域
return qsort(nums, l, left, k - b - c); // 否則在小于基準值的區(qū)域繼續(xù)查找
}
/**
* 交換數(shù)組中兩個元素的位置
*
* @param nums 輸入的整數(shù)數(shù)組
* @param i 第一個元素的索引
* @param j 第二個元素的索引
*/
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
LCR 159. 庫存管理 III - 力扣（LeetCode）
算法分析
本道題其實與前面的找第k個最大元素類似，我們依舊可以使用排序，然后有另一個數(shù)組記錄[0,k]期間的數(shù)，但本道題我們可以采用分治的思想，利用快排來解決。
算法步驟
當我們完成上述的過程后，我們需要利用一個大小為k的數(shù)組ret來接收nums數(shù)組中【0，k】區(qū)間的數(shù).
算法代碼
class Solution {
/**
* 庫存管理函數(shù)，通過快速排序算法對庫存進行管理
*
* @param stock 庫存數(shù)據(jù)數(shù)組
* @param cnt 需要管理的庫存項數(shù)量
* @return 管理后的庫存數(shù)組
*/
public int[] inventoryManagement(int[] stock, int cnt) {
// 使用快速排序?qū)齑鏀?shù)組進行排序
qsort(stock, 0, stock.length - 1, cnt);
// 創(chuàng)建一個新的數(shù)組來存儲管理后的庫存數(shù)據(jù)
int[] ret = new int[cnt];
// 將排序后的庫存數(shù)據(jù)的前cnt個元素復制到新的數(shù)組中
for(int i=0;i ret[i] = stock[i]; } // 返回管理后的庫存數(shù)組 return ret; } /** * 交換數(shù)組中兩個元素的位置 * * @param nums 數(shù)組 * @param left 左側(cè)元素索引 * @param right 右側(cè)元素索引 */ public void swap(int[] nums, int left, int right){ int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } /** * 快速排序算法的實現(xiàn) * * @param nums 待排序的數(shù)組 * @param left 排序開始的左側(cè)索引 * @param right 排序結(jié)束的右側(cè)索引 * @param k 需要管理的庫存項數(shù)量，用于決定排序的范圍 */ private void qsort(int[] nums, int left, int right, int k){ if(left >= right) return; int key = nums[new Random().nextInt(right - left + 1) + left]; int i = left, L = left - 1, R = right + 1; while(i < R){ if(nums[i] else if(nums[i]==key) i++; else swap(nums,i,--R); } // 根據(jù)分區(qū)結(jié)果，決定下一步的查找范圍 int a=L-left+1; int b=R-L-1; if(a>=k) qsort(nums,left,L,k); else if(a+b>=k) return; else qsort(nums,R,right,k-a-b); } } 以上就是采用分治思想使用快排的一些題目。 本篇就先到這里啦~下一篇將為大家講解采用歸并排序如何解決一些算法題目。 若有不足，歡迎指正~ ? 柚子快報激活碼778899分享：【算法專場】分治（上） 相關文章
本文內(nèi)容根據(jù)網(wǎng)絡資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權，聯(lián)系刪除。
Fruugo環(huán)球購物
