算法學習筆記：18.拉斯維加斯算法 ——從原理到實戰，涵蓋 LeetCode 與考研 408 例題

在隨機化算法領域，拉斯維加斯（Las Vegas）算法以其獨特的設計思想占據重要地位。與蒙特卡洛（Monte Carlo）算法不同，拉斯維加斯算法總能給出正確的結果，但運行時間具有隨機性 —— 在最壞情況下可能很長，但平均性能往往優于確定性算法。

拉斯維加斯算法核心思路

算法定義與特點

拉斯維加斯算法是一類隨機化算法，其核心特征可概括為：

正確性保障：無論隨機選擇如何，算法最終一定能返回正確結果。

時間隨機性：算法的運行時間取決于隨機選擇的路徑，可能存在極端情況，但平均時間復雜度通常較優。

驗證步驟：算法往往包含 “隨機嘗試 - 驗證結果” 的過程，若驗證失敗則重新嘗試，直至成功。

與其他算法的對比可用下表展示：

算法類型	正確性	時間確定性	典型應用
確定性算法	總是正確	時間確定	冒泡排序、二分查找
蒙特卡洛算法	可能錯誤（有誤差界）	時間確定	素數測試、近似計數
拉斯維加斯算法	總是正確	時間隨機	隨機化快速排序、洗牌

?算法流程

拉斯維加斯算法的典型流程可分為三個階段：

隨機選擇：根據問題特性生成隨機決策（如隨機選擇 pivot、隨機交換元素）。

執行操作：基于隨機選擇執行算法核心邏輯（如分區、搜索）。

驗證結果：檢查當前結果是否滿足問題要求，若滿足則返回，否則回到步驟 1 重新嘗試。

其流程可用以下流程圖表示：

1.3 優勢與適用場景

優勢：無需處理最壞情況的極端輸入（通過隨機性規避），平均性能優異，實現簡單。

適用場景：解決具有 “解存在且可驗證” 特性的問題，如組合優化、搜索、排序等。

LeetCode 例題實戰

例題 1：384. 打亂數組（中等）

題目描述：給你一個整數數組 nums ，設計算法來打亂一個沒有重復元素的數組。打亂后，數組的所有排列應該是等可能的。實現 Solution 類：
Solution(int[] nums) 使用整數數組 nums 初始化對象。
int[] reset() 重設數組到它的初始狀態并返回。
int[] shuffle() 返回數組隨機打亂后的結果。

示例：

輸入

["Solution", "shuffle", "reset", "shuffle"]

[[[1, 2, 3]], [], [], []]

輸出

[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解題思路：采用 Fisher-Yates 洗牌算法（拉斯維加斯算法的典型應用），通過隨機交換元素實現等概率打亂：

遍歷數組，對每個位置 i，隨機選擇 [i, n-1] 范圍內的索引 j。

交換 nums[i] 與 nums[j]，確保每個元素出現在任意位置的概率相等。

由于每次隨機選擇均能生成有效排列，無需驗證步驟，直接返回結果。

算法圖示：洗牌過程（以 [1,2,3] 為例）

代碼實現：

class Solution {private int[] original; // 保存初始數組private int[] shuffled; // 保存打亂后的數組private Random random;public Solution(int[] nums) {original = nums.clone();shuffled = nums.clone();random = new Random();}// 重置數組到初始狀態public int[] reset() {shuffled = original.clone();return shuffled;}// 打亂數組（Fisher-Yates洗牌算法）public int[] shuffle() {int n = shuffled.length;for (int i = 0; i < n; i++) {// 隨機選擇[i, n-1]范圍內的索引int j = i + random.nextInt(n - i);// 交換元素swap(shuffled, i, j);}return shuffled;}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}

復雜度分析：

時間復雜度：shuffle() 為 O (n)，需遍歷數組并執行 O (1) 交換；reset() 為 O (n)，需復制數組。

空間復雜度：O (n)，需存儲初始數組和打亂后的數組。

隨機性：通過均勻隨機選擇索引，保證所有排列等概率出現，滿足題目要求。

例題 2：215. 數組中的第 K 個最大元素（中等）

題目描述：給定整數數組 nums 和整數 k，請返回數組中第 k 個最大的元素。請注意，你需要找的是數組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。

示例：

輸入: [3,2,1,5,6,4] 和 k = 2

輸出: 5

解題思路：采用隨機化快速選擇算法（拉斯維加斯算法的變種）：

隨機選擇 pivot：避免對有序數組的最壞情況，隨機選擇基準元素。

分區操作：將數組分為 “小于 pivot”“等于 pivot”“大于 pivot” 三部分。

驗證與遞歸：根據 pivot 位置判斷是否為目標元素，若不是則遞歸搜索對應子數組。由于 pivot 隨機選擇，平均時間復雜度為 O (n)。

算法圖示：查找 [3,2,1,5,6,4] 中第 2 大元素（5）的過程

代碼實現：

import java.util.Random;class Solution {private Random random = new Random();public int findKthLargest(int[] nums, int k) {int n = nums.length;int targetIndex = n - k; // 第k大元素在有序數組中的索引return quickSelect(nums, 0, n - 1, targetIndex);}private int quickSelect(int[] nums, int left, int right, int target) {if (left == right) {return nums[left]; // 基線條件：子數組長度為1}// 隨機選擇pivot并分區int pivotIndex = randomPartition(nums, left, right);// 驗證pivot位置是否為目標if (pivotIndex == target) {return nums[pivotIndex];} else if (pivotIndex < target) {// 目標在右子數組return quickSelect(nums, pivotIndex + 1, right, target);} else {// 目標在左子數組return quickSelect(nums, left, pivotIndex - 1, target);}}// 隨機選擇pivot并執行分區private int randomPartition(int[] nums, int left, int right) {// 隨機選擇[left, right]范圍內的索引作為pivotint pivotPos = left + random.nextInt(right - left + 1);// 將pivot交換到數組末尾swap(nums, pivotPos, right);return partition(nums, left, right);}// 分區操作（類似快速排序）private int partition(int[] nums, int left, int right) {int pivot = nums[right];int i = left - 1; // 小于pivot區域的邊界for (int j = left; j < right; j++) {if (nums[j] <= pivot) {i++;swap(nums, i, j);}}// 將pivot放到最終位置swap(nums, i + 1, right);return i + 1;}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}

復雜度分析：

時間復雜度：平均 O (n)，最壞 O (n2)（但隨機化后概率極低）。

空間復雜度：O (logn)，來自遞歸棧（平均情況）。

隨機性：通過隨機選擇 pivot，避免有序數組導致的 O (n2) 最壞情況，確保平均性能。

考研 408 例題解析

例題 1：概念辨析題（選擇題）

題目：下列關于拉斯維加斯算法的敘述中，正確的是（）。
A. 拉斯維加斯算法可能返回錯誤結果，但錯誤概率可控制
B. 拉斯維加斯算法的運行時間是確定的，與輸入無關
C. 拉斯維加斯算法通過隨機性確保最壞情況下的時間復雜度最優
D. 拉斯維加斯算法適用于 “解存在且可驗證” 的問題

答案：D

解析：

A 錯誤：拉斯維加斯算法總是返回正確結果，蒙特卡洛算法可能返回錯誤結果。

B 錯誤：拉斯維加斯算法的運行時間是隨機的，取決于隨機選擇。

C 錯誤：拉斯維加斯算法不能保證最壞情況時間復雜度，但能通過隨機性優化平均復雜度。

D 正確：拉斯維加斯算法的 “隨機嘗試 - 驗證” 流程要求解存在且可驗證。

例題 2：算法設計題（應用題）

題目：設計一個拉斯維加斯算法，在有序數組 arr 中查找目標值 target，要求平均時間復雜度優于 O (n)。若數組中存在 target，返回其索引；否則返回 -1。

解題思路：

隨機采樣驗證：利用數組有序性，隨機選擇索引 i 并檢查 arr[i] 與 target 的大小。

縮小搜索范圍：若 arr[i] < target，則目標只可能在 i+1 右側；若 arr[i] > target，則目標只可能在 i-1 左側。

遞歸或迭代：重復步驟 1-2 縮小范圍，直至找到目標或范圍為空。若隨機采樣均勻，平均時間復雜度為 O (logn)。

代碼實現：

import java.util.Random;public class RandomizedSearch {private Random random = new Random();public int search(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {if (left == right) {return arr[left] == target ? left : -1;}// 隨機選擇范圍內的索引int i = left + random.nextInt(right - left + 1);if (arr[i] == target) {return i; // 找到目標} else if (arr[i] < target) {left = i + 1; // 縮小范圍到右側} else {right = i - 1; // 縮小范圍到左側}}return -1; // 目標不存在}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9, 11, 13};RandomizedSearch solver = new RandomizedSearch();System.out.println(solver.search(arr, 7)); // 可能返回3System.out.println(solver.search(arr, 4)); // 返回-1}}

復雜度分析：