排序应用题：H指数、摆动排序与修车问题

H 指数（LeetCode 274）

H 指数：至少有 H 篇论文各被引用 ≥ H 次。

解法一：排序后枚举（O(n log n)）

public int hIndex(int[] citations) {
    Arrays.sort(citations);
    int n = citations.length;
    for (int i = 0; i < n; i++) {
        int h = n - i;          // 从右往左，还剩 h 篇
        if (citations[i] >= h) return h;
    }
    return 0;
}

解法二：计数排序（O(n)）

public int hIndex(int[] citations) {
    int n = citations.length;
    int[] count = new int[n + 1];
    for (int c : citations) count[Math.min(c, n)]++;
    int total = 0;
    for (int i = n; i >= 0; i--) {
        total += count[i];
        if (total >= i) return i;
    }
    return 0;
}

摆动排序（LeetCode 280/324）

280：原地调整，奇数位>相邻偶数位

规律：对于偶数下标 i，若 nums[i] > nums[i+1]，交换；奇数下标 i，若 nums[i] < nums[i+1]，交换。

public void wiggleSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        if ((i % 2 == 0 && nums[i] > nums[i+1]) ||
            (i % 2 == 1 && nums[i] < nums[i+1])) {
            int tmp = nums[i]; nums[i] = nums[i+1]; nums[i+1] = tmp;
        }
    }
}

324：摆动排序 II（确保 nums[i-1] < nums[i] > nums[i+1]）

找中位数，三路划分 + 间隔放置。

public void wiggleSort(int[] nums) {
    int n = nums.length;
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    int mid = (n - 1) / 2;
    // 小数放偶数位（0,2,4...），大数放奇数位（1,3,5...）
    int lo = mid, hi = n - 1;
    for (int i = 0; i < n; i++) {
        nums[i] = (i % 2 == 0) ? sorted[lo--] : sorted[hi--];
    }
}

修车的最少时间（LeetCode 2594）

多个工人 mechanic[i] 修一辆车需 mechanic[i] * k² 分钟（k 是该工人已修台数）。

二分答案：二分时间 t，验证是否能修完 n 辆车。

public long repairCars(int[] ranks, int cars) {
    long lo = 1, hi = (long) ranks[0] * cars * cars;
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (canFinish(ranks, cars, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

private boolean canFinish(int[] ranks, int cars, long t) {
    long total = 0;
    for (int r : ranks) {
        total += (long) Math.sqrt(t / r);
        if (total >= cars) return true;
    }
    return false;
}

数组排列后最大值（LeetCode 942）

给定 DI 字符串，输出满足条件的最小字典序排列。

public int[] diStringMatch(String s) {
    int lo = 0, hi = s.length();
    int[] res = new int[s.length() + 1];
    for (int i = 0; i < s.length(); i++) {
        res[i] = s.charAt(i) == 'I' ? lo++ : hi--;
    }
    res[s.length()] = lo;   // lo == hi
    return res;
}

小结