关于算法:4寻找两个正序数组的中位数

42次阅读

共计 1442 个字符,预计需要花费 4 分钟才能阅读完成。

/**
 * 4. 寻找两个正序数组的中位数
 * 给定两个大小别离为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数。*
 * 算法的工夫复杂度应该为 O(log (m+n))
 *
 */
public class Median {public static double findMedianElement(int[] numArray1, int[] numArray2) {
        int length1 = numArray1.length, length2 = numArray2.length;
        int totalLength = length1 + length2;
        // 奇数
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double median = getElement(numArray1, numArray2, midIndex + 1);
            return median;
        } else {
            // 偶数
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            int k1 = getElement(numArray1, numArray2, midIndex1 + 1);
            int k2 = getElement(numArray1, numArray2, midIndex2 + 1);
            double median = (k1 + k2) / 2.0;
            return median;
        }
    }

    public static int getElement(int[] numArray1, int[] numArray2, int k) {
        int length1 = numArray1.length, length2 = numArray2.length;
        int index1 = 0, index2 = 0;
        // 长期存储 K
        int kTemp = k;
        // 记录遍历次数
        int count = 0;
        while (true) {
            // 非凡状况,取第一个元素
            if (k == 1) {if (length1 == 0){return numArray2[index2];
                }
                if (length2 == 0){return numArray1[index1];
                }
                return Math.min(numArray1[index1], numArray2[index2]);
            }
            // 元素初始值
            int pivot1 = -99999, pivot2 = -99999;
            // 数组 1,下标没有越界,且数组个数大于 0
            if (index1 <= length1 -1 && length1 > 0){pivot1 = numArray1[index1];
            }
            // 数组 2,下标没有越界,且数组个数大于 0
            if (index2 <= length2 -1 && length2 > 0){pivot2 = numArray2[index2];
            }
            // 曾经遍历了 k- 1 次 等同于 曾经找到了指标元素
            if(count == (kTemp-1)){if (index1 > length1 - 1) {return pivot2;}
                if (index2 > length2 - 1) {return pivot1;}
                return Math.min(pivot1,pivot2);
            }
            // 谁的元素小,谁挪动指针
            if ((pivot1 != -99999 && pivot2 != -99999 && pivot1 <= pivot2) ||
                    pivot2 == -99999
            ) {
                // 右移 nums1 指针
                index1 += 1;
                // 记录遍历次数
                count += 1;
            } else {
                // 右移 nums2 指针
                index2 += 1;
                // 记录遍历次数
                count += 1;

            }
        }
    }

正文完
 0