跳到主要内容

分治算法

问题​

分治算法的原理和常见题目有哪些？

答案​

分治三步：分解 → 求解子问题 → 合并。

归并排序（经典分治）​

分治排序 O(n log n)
public void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

private void merge(int[] arr, int left, int mid, int right) {
    int[] tmp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= right) tmp[k++] = arr[j++];
    System.arraycopy(tmp, 0, arr, left, tmp.length);
}

快速选择（第 K 大/小元素）​

基于 partition 的快速选择 O(n) 平均
public int findKthLargest(int[] nums, int k) {
    int target = nums.length - k;  // 第 k 大 = 第 n-k 小
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int pivot = partition(nums, left, right);
        if (pivot == target) return nums[pivot];
        else if (pivot < target) left = pivot + 1;
        else right = pivot - 1;
    }
    return nums[left];
}

private int partition(int[] nums, int left, int right) {
    // 随机选择 pivot 避免最坏情况
    int randIdx = left + new Random().nextInt(right - left + 1);
    swap(nums, randIdx, right);
    
    int pivot = nums[right], i = left;
    for (int j = left; j < right; j++) {
        if (nums[j] <= pivot) swap(nums, i++, j);
    }
    swap(nums, i, right);
    return i;
}

数组中的逆序对（剑指 Offer 51）​

归并排序过程中统计逆序对
int count = 0;

public int reversePairs(int[] nums) {
    mergeCount(nums, 0, nums.length - 1);
    return count;
}

private void mergeCount(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeCount(arr, left, mid);
    mergeCount(arr, mid + 1, right);
    
    int[] tmp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            count += mid - i + 1;  // arr[i..mid] 都比 arr[j] 大 → 逆序对
            tmp[k++] = arr[j++];
        }
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= right) tmp[k++] = arr[j++];
    System.arraycopy(tmp, 0, arr, left, tmp.length);
}

Pow(x, n)（LeetCode 50）​

快速幂 O(log n)
public double myPow(double x, int n) {
    long N = n;
    if (N < 0) { x = 1 / x; N = -N; }
    double result = 1.0;
    while (N > 0) {
        if ((N & 1) == 1) result *= x;
        x *= x;
        N >>= 1;
    }
    return result;
}

常见面试问题​

Q1: 分治和递归的关系？​

答案：

分治是算法思想（分解 → 求解 → 合并），递归是实现手段。分治通常用递归实现，但也可以用迭代（如自底向上归并排序）。

Q2: 快速选择 vs 堆排序求 TopK？​

答案：

方法平均时间最坏时间空间
快速选择O(n)O(n)O(n2)O(n^2)O(1)O(1)
小顶堆O(nlog⁡k)O(n \log k)O(nlog⁡k)O(n \log k)O(k)O(k)

快速选择平均更快，但最坏退化；堆方法稳定，适合数据流。

Q3: 归并排序的稳定性？​

答案：

归并排序是稳定的（合并时相等元素保持原序），这也是 Arrays.sort() 对对象数组使用 TimSort（基于归并）的原因。

相关链接​