掌握Java实现乱序数组中位数的几种方法

在Java中，求乱序数组的中位数是一个常见的编程问题。由于数组是乱序的，我们不能直接对数组进行排序然后简单地取中间的数作为中位数。以下是一些实现乱序数组中位数的方法：

1. 直接排序法

最直接的方法是对数组进行排序，然后取中间的数。这种方法的时间复杂度为O(n log n)，其中n是数组的长度。

import java.util.Arrays;

public class MedianFinder {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] merged = new int[nums1.length + nums2.length];
        System.arraycopy(nums1, 0, merged, 0, nums1.length);
        System.arraycopy(nums2, 0, merged, nums1.length, nums2.length);
        Arrays.sort(merged);
        int mid = merged.length / 2;
        if (merged.length % 2 == 0) {
            return (merged[mid - 1] + merged[mid]) / 2.0;
        } else {
            return merged[mid];
        }
    }
}

2. 快速选择算法（Quickselect）

快速选择算法是寻找第k小元素的有效方法，它的平均时间复杂度是O(n)。以下是使用快速选择算法来找到中位数的实现：

public class MedianFinder {
    public int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        int pivotIndex = partition(nums, left, right);
        if (k == pivotIndex) {
            return nums[k];
        } else if (k < pivotIndex) {
            return quickSelect(nums, left, pivotIndex - 1, k);
        } else {
            return quickSelect(nums, pivotIndex + 1, right, k);
        }
    }

    private int partition(int[] nums, int left, int right) {
        int pivot = nums[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, i, right);
        return i;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public double findMedian(int[] nums1, int[] nums2) {
        int totalLength = nums1.length + nums2.length;
        if (totalLength % 2 == 1) {
            return quickSelect(merge(nums1, nums2), 0, totalLength - 1, totalLength / 2);
        } else {
            return (quickSelect(merge(nums1, nums2), 0, totalLength - 1, totalLength / 2 - 1) +
                    quickSelect(merge(nums1, nums2), 0, totalLength - 1, totalLength / 2)) / 2.0;
        }
    }

    private int[] merge(int[] nums1, int[] nums2) {
        int[] merged = new int[nums1.length + nums2.length];
        int i = 0, j = 0, k = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }
        while (i < nums1.length) {
            merged[k++] = nums1[i++];
        }
        while (j < nums2.length) {
            merged[k++] = nums2[j++];
        }
        return merged;
    }
}

3. 双指针法

如果数组元素是整数，并且我们可以接受浮点数作为结果，双指针法是一种简单的方法。这种方法的时间复杂度是O(n)。

public class MedianFinder {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int totalLength = nums1.length + nums2.length;
        int left = (totalLength - 1) / 2;
        int right = totalLength / 2;
        int i = Math.max(0, left);
        int j = Math.max(0, right);
        int maxLeft = 0;
        int minRight = 0;
        while (true) {
            if (i < nums1.length && j < nums2.length) {
                if (nums1[i] < nums2[j]) {
                    maxLeft = Math.max(maxLeft, nums1[i++]);
                    minRight = nums2[j++];
                } else {
                    maxLeft = Math.max(maxLeft, nums2[j++]);
                    minRight = nums1[i++];
                }
            } else if (i < nums1.length) {
                maxLeft = Math.max(maxLeft, nums1[i++]);
                minRight = nums2[j++];
            } else {
                maxLeft = Math.max(maxLeft, nums2[j++]);
                minRight = nums1[i++];
            }
            if (i == left + 1 && j == right + 1) {
                return totalLength % 2 == 0 ? (maxLeft + minRight) / 2.0 : maxLeft;
            }
        }
    }
}

这些方法各有优缺点，你可以根据具体需求选择合适的方法。希望这些实现能帮助你更好地理解和应用这些算法。