主页 / 问题 / 1440063
Accepted
Kalmankantaja
Asked:2022-08-17 14:56:52 +0000 UTC2022-08-17 14:56:52 +0000 UTC

如何加快返回两个排序数组中位数的代码？

  • 772

使用 leetcode 完成任务。任务文本：

给定两个大小分别为 m 和 n 的排序数组 nums1 和 nums2，返回两个排序数组的中位数。总体运行时复杂度应为 O(log (m+n))。

我已经解决了这个问题，但我想实现最快的解决方案。目前，我已经为自己160 ms和39.2 MB. 如何使代码在速度和内存消耗方面更加优化？

public class Solution
{
    public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        nums1 = Concat(nums1, nums2);
        SortArray(nums1, 0, nums1.Length - 1);
  
        if (nums1.Length % 2 == 0)
        {
            double a = nums1[nums1.Length / 2 - 1];
            double b = nums1[nums1.Length / 2];
            double result = (a + b) / 2;
            return result;
        }
        return Convert.ToDouble(nums1[nums1.Length / 2]);

    }
    private int[] Concat(int[] x, int[] y)
    {
        int oldLen = x.Length;
        Array.Resize(ref x, x.Length + y.Length);
        Array.Copy(y, 0, x, oldLen, y.Length);
        return x;
    }
    private void SortArray(int[] array, int leftIndex, int rightIndex)
    {
        var i = leftIndex;
        var j = rightIndex;
        var pivot = array[leftIndex];
        while (i <= j)
        {
            while (array[i] < pivot)
            {
                i++;
            }

            while (array[j] > pivot)
            {
                j--;
            }
            if (i <= j)
            {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
        }

        if (leftIndex < j)
            SortArray(array, leftIndex, j);
        if (i < rightIndex)
            SortArray(array, i, rightIndex);
    }
}
c# оптимизация

2 个回答

  1. Best Answer

    解决方案

    NB从头开始​​索引数组。序数统计也从零开始编号。

    数组和的并集中的nums1[i]第 - 阶统计信息是真的吗？knums1nums2

    让我们计算一下j = k - i。如果合并数组前面确实nums1[i]有j元素nums2，那么答案是肯定的。为此，满足不等式就足够了nums2[j - 1] <= nums1[i] <= nums2[j]。如果满足，那么nums1[i]将正好有j元素 fromnums2和i元素 from nums1。而他本人将用数字j + i（= k）就位。

    让我们定义一个CheckOrderStatistic(nums1, nums2, i, k)返回0if nums1[i]-th korder 统计信息的方法。-1如果违反了条件并且违反了条件，nums1[i] <= nums2[j]它也会返回。1nums2[j - 1] <= nums1[i]

    例子：

    nums1 = [0, 1, 3, 4, 6, 7]... nums2 = [2, 5]_k = 3

    i                                          0  1  2  3  4  5
CheckOrderStatistic(nums1, nums2, i, k)   -1 -1  0  1  1  1

    随着值的增加，您可以对i. 寻找零。它可能不存在。这意味着k数组中的一个元素就位nums2。在这种情况下，交换nums1并nums2执行另一个二进制搜索。

    该算法的复杂性O(log(m) + log(n))是 ，其中m和n是数组的长度。就大O(log(m) + log(n)) = O(log(m + n))O而言。任务条件需要什么。

    比较

    您不会比排序解决方案更快地找到此解决方案。数组不超过 1000 个元素。在这些大小下，将程序加载到内存中需要花费所有时间。160 毫秒和 39.2 MB 都是 C# 运行时消耗的时间和内存。例如，任务中数组的内存不超过 8 KB。8 KB 在 40 兆字节的背景上。随着时间的推移，同样的情况 - 在毫秒的背景下，排序将花费微秒。没什么好谈的。在讨论 Litcode 的解决方案时，一切都是完全排序的，有时是合并的，这并非没有道理。

    衡量解决方案之间的差异需要数百万或数十亿个元素。然后很明显二进制搜索更快。前提是测量解决问题的一个函数的执行时间，而不是测量整个程序的执行时间。

    编码

    该代码通过了 Litcode 上的所有测试。在内存和速度方面，处于中间位置。为什么-我在上面解释过。

    public class Solution {
    
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.Length + nums2.Length;
        int k1 = (n - 1) / 2;
        int k2 = (n - 1) - k1;
        double s1 = OrderStatistic(nums1, nums2, k1);
        double s2 = OrderStatistic(nums1, nums2, k2);
        return (s1 + s2) / 2;
    }

    // checks if nums1[i] is k-th order statistic in merged array
    private int CheckOrderStatistic(int[] nums1, int[] nums2, int i, int k) {
        int j = k - i;

        if (j < 0) {
            return 1;
        }
        if (nums2.Length < j) {
            return -1;
        }

        // nums2[j - 1] <= nums1[i]
        if (0 < j && nums2[j - 1] > nums1[i]) {
            return -1;
        }

        // nums1[i] <= nums2[j]
        if (j < nums2.Length && nums1[i] > nums2[j]) {
            return 1;
        }

        return 0;
    }

    private int Search(int[] nums1, int[] nums2, int k) {
        if (nums1.Length == 0) {
            return -1;
        }
        int lo = 0;
        int hi = nums1.Length - 1;
        int r_lo = CheckOrderStatistic(nums1, nums2, lo, k);
        if (r_lo == 0) {
            return lo;
        }
        if (r_lo > 0) {
            return -1;
        }
        int r_hi = CheckOrderStatistic(nums1, nums2, hi, k);
        if (r_hi == 0) {
            return hi;
        }
        if (r_hi < 0) {
            return -1;
        }
        while(lo < hi - 1) {
            int mid = (lo + hi) / 2;
            int r_mid = CheckOrderStatistic(nums1, nums2, mid, k);
            if (r_mid == 0) {
                return mid;
            }
            if (r_mid < 0) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return -1;
    }

    private int OrderStatistic(int[] nums1, int[] nums2, int k) {
        int i1 = Search(nums1, nums2, k);
        if (i1 != -1) {
            return nums1[i1];
        }
        int i2 = Search(nums2, nums1, k);
        return nums2[i2];
    }
}
    • 4

  2. 要解决这个问题，就需要双二进制（binary）搜索。

    表示原始数组 A[1..n] 和 B[1..m]。然后我们需要找到一个数 X，使得 A 和 B 中 ≤ X 的元素数为 (n+m)/2（如果该数不是整数，则允许进行四舍五入）。

    让我们尝试在第一个数组中查找这个数字。让我们从 X=A[i] 开始，找出数组 B ≤ X 中有多少个元素，让这个数字等于 j = j(i)。由于数组 B 是有序的，所以这个数可以通过二分查找找到。但是现在两个数组中 ≤ X 的元素数是 i + j。

    请注意，结果函数 f(i) = i + j(i) 是单调的。所以，你可以通过再二分查找在它的值中找到想要的(n + m) / 2。如果找到了，那么 A[i] 就是中位数。

    也有可能在 f(i) 的值中没有 (n+m)/2，而只有更小的值。这意味着所需的中位数位于数组 B 中。让我们表示 f(i) < (n+m)/2 的最大值 i（这样的 i 应该已经在上一步中通过不成功的二分搜索找到） , 那么中位数应该是 B [(n+m)/2 - i]

    • 3

相关问题