抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

LeetCode-4.寻找两个正序数组的中位数-C

LeetCode-C

发布于：2024年11月30日

次浏览

1.寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

1
2
3
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
1
2
3
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int ums2Size) {
    
}

2.个人思路

​ 题目要求时间复杂度为O(log (m+n))，查询资料发现，此处应该使用while循环。

2.1时间复杂度

  • 常数阶O(1)

    无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)

    1
    2
    3
    4
    5
    int i = 1;
    int j = 2;
    ++i;
    j++;
    int m = i + j;

  • 线性阶O(n)

    for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

    1
    2
    3
    4
    5
    for(i=1; i<=n; ++i)
    {
       j = i;
       j++;
    }

  • 对数阶O(logN)

    在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)

    1
    2
    3
    4
    5
    int i = 1;
    while(i<n)
    {
        i = i * 2;
    }

  • 线性对数阶O(nlogN)

    将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

    1
    2
    3
    4
    5
    6
    7
    8
    for(m=1; m<n; m++)
    {
        i = 1;
        while(i<n)
        {
            i = i * 2;
        }
    }

  • 平方阶O(n2)

    把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

    1
    2
    3
    4
    5
    6
    7
    8
    for(x=1; i<=n; x++)
    {
       for(i=1; i<=n; i++)
        {
           j = i;
           j++;
        }
    }

2.2个人代码（没写出来）

​ 不愧是困难的题目，想了两个小时，改来改去，但都是不行。主要问题是边界处理不好，对有的数组管用，但是条件苛刻一点的话，就不行。第一种想的比较简答，但是会出现数据遗漏，因为当一个数组走到最后一个后，那一位是2，但是另外一个数组是3,4,5的话，就一直是2比3小，数据就丢失了，全都变为了2。第二种是准备加入一个最后一位的处理，只要有一个数组走到最后一位后，并且在另一个数组里面找到了比他大的，就完全可以拷贝剩下的了，不需要判断。感觉再想个两个小时就能差不多了，但是越写越偏离算法了，就像是不断debug调试出来的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int num = nums1Size+nums2Size;
    int temp[num];
    int i = 0,j = 0;
    double ret;
    bool  last;
    while(num)
    {
        if(i == nums1Size || j == nums2Size) last=true;

        if(nums1[i] >= nums2[j])
        {
            if(!last)
            {
                temp[nums1Size+nums2Size-num] = nums2[j];
                printf(" > temp[%d]:%d num = %d j=%d \n",nums1Size+nums2Size-num,temp[nums1Size+nums2Size-num],num,j);
                j++;
                num--;
            }
            else
            {
                temp[nums1Size+nums2Size-num] = nums1[i];
                num--;
                i++;
            }
            continue;
        }
        if(nums1[i] <= nums2[j])
        {
            if(!last)
            {
                temp[nums1Size+nums2Size-num] = nums1[i];
                printf(" < temp[%d]:%d num = %d i= %d\n",nums1Size+nums2Size-num,temp[nums1Size+nums2Size-num],num,i);
                i++;
                num--;
            }
            else
            {
                temp[nums1Size+nums2Size-num] = nums1[j];
                num--;
                j++;
            }
            continue;
        }
    }

    if((nums1Size+nums2Size)%2 != 0 )
    {
        //printf("jishu");
        ret = temp[(nums1Size+nums2Size-1)/2];//奇数个

    }else{
       // printf("%d  %d ",temp[(nums1Size+nums2Size-2)/2],temp[(nums1Size+nums2Size-2)/2+1]);
        ret = (temp[(nums1Size+nums2Size-2)/2]+temp[(nums1Size+nums2Size-2)/2+1])/2.0;//偶数个
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
        int num = nums1Size+nums2Size;
    int temp[num];
    int i = 0,j = 0;
    double ret;
    while(num)
    {
        if(i == nums1Size) i= nums1Size-1;
        if(j == nums2Size) j= nums2Size-1;
        if(nums1[i] >= nums2[j])
        {
            temp[nums1Size+nums2Size-num] = nums2[j];
            if(i == nums1Size-1 && j== nums2Size-1)  //最后一位  i = 1, j = 0  需要处理两次
            {
                temp[nums1Size+nums2Size-num]= nums2[j];
                num--;
                temp[nums1Size+nums2Size-num]= nums1[i];
                break;
            }
            j++;
            num--;
            continue;
        }
        if(nums1[i] <= nums2[j])
        {
            if(i == nums1Size-1 && j== nums2Size-1)  //最后一位  i = 1, j = 0  需要处理两次
            {

                temp[nums1Size+nums2Size-num]= nums1[i];
                num--;
                temp[nums1Size+nums2Size-num]= nums2[j];
                break;
            }

            temp[nums1Size+nums2Size-num] = nums1[i];
            i++;
            num--;
            continue;
        }
    }

    if((nums1Size+nums2Size)%2 != 0 )
    {
        ret = temp[(nums1Size+nums2Size-1)/2];//奇数个

    }else{
        ret = (temp[(nums1Size+nums2Size-2)/2]+temp[(nums1Size+nums2Size-2)/2+1])/2.0;//偶数个
    }
    return ret;
}

有了新思路，但是时间复杂度达不到要求。但可以有效解题：

可以先合并两个数组，不考虑大小的合并。然后排序。排序后就可以return。

或者，在一开始思路上不考虑最后一位，分类到中位数就行了。没必要考虑排序好全部数组。。。。

3.官方解析

二分法：不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 0 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。

假设两个有序数组的长度分别为 m 和 n，根据中位数的定义，当 m+n 是奇数时，中位数是两个有序数组中的第 (m+n)/2 个元素，当 m+n 是偶数时，中位数是两个有序数组中的第 (m+n)/2 个元素和第 (m+n)/2+1 个元素的平均值。因此，这道题可以转化成寻找两个有序数组中的第 k 小的数，其中 k 为 (m+n)/2 或 (m+n)/2+1。

假设两个有序数组分别是 A 和 B。要找到第 k 个元素，我们可以比较 A[k/2−1] 和 B[k/2−1]，其中 / 表示整数除法。由于 A[k/2−1] 和 B[k/2−1] 的前面分别有 A[0..k/2−2] 和 B[0..k/2−2]，即 k/2−1 个元素，对于 A[k/2−1] 和 B[k/2−1] 中的较小值，最多只会有 (k/2−1)+(k/2−1)≤k−2 个元素比它小，那么它就不能是第 k 小的数了。

因此我们可以归纳出三种情况：

  • 如果 A[k/2−1]<B[k/2−1]，则比 A[k/2−1] 小的数最多只有 A 的前 k/2−1 个数和 B 的前 k/2−1 个数，即比 A[k/2−1] 小的数最多只有 k−2 个，因此 A[k/2−1] 不可能是第 k 个数，A[0] 到 A[k/2−1] 也都不可能是第 k 个数，可以全部排除。

  • 如果 A[k/2−1]>B[k/2−1]，则可以排除 B[0] 到 B[k/2−1]。

  • 如果 A[k/2−1]=B[k/2−1]，则可以归入第一种情况处理。

可以看到，比较 A[k/2−1] 和 B[k/2−1] 之后，可以排除 k/2 个不可能是第 k 小的数，查找范围缩小了一半。同时，我们将在排除后的新数组上继续进行二分查找，并且根据我们排除数的个数，减少 k 的值，这是因为我们排除的数都不大于第 k 小的数。

有以下三种情况需要特殊处理：

  • 如果 A[k/2−1] 或者 B[k/2−1] 越界，那么我们可以选取对应数组中的最后一个元素。在这种情况下，我们必须根据排除数的个数减少 k 的值，而不能直接将 k 减去 k/2。

  • 如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 k 小的元素。

  • 如果 k=1，我们只要返回两个数组首元素的最小值即可。

转自官方4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 寻找第K大的数，二分排除查找，通过排除查找K大的数
// 思路：1、先看k/2 位置AB两个数组元素的大小，可以排除k/2个，此处有2种情况 AB都在范围，AB其一不在范围
int min(int k1, int k2)
{
    if (k1 < k2) {
        return k1;
    }
    return k2;
}
// 寻找第K大的元素，
double GetKValue(int* nums1, int nums1Size, int* nums2, int nums2Size, int k)
{
    int index1 = 0;
    int index2 = 0;
    while(true) {
        // 数组1全部遍历完成
        if (index1 == nums1Size) {
            return nums2[index2 + k - 1];
        }
        // 数组2全部遍历完成
        if (index2 == nums2Size) {
            return nums1[index1 + k - 1];
        }
        // 最终K减小到1,取两者之中的小的那个返回
        if (k == 1) {
            return min(nums2[index2 + k - 1], nums1[index1 + k - 1]);
        }

        // 正常逻辑判断
        int mind = k / 2;
        int newIndex1 = min(index1 + mind, nums1Size) - 1;
        int newIndex2 = min(index2 + mind, nums2Size) - 1;
        if (nums1[newIndex1] < nums2[newIndex2]) {
            k -=  (newIndex1 - index1 + 1);
            index1 = newIndex1 + 1;
        } else {
            k -= (newIndex2 - index2 + 1);
            index2 = newIndex2 + 1;
        }
    }
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int num = nums1Size + nums2Size;
    int flag = num & 0x01;
    // 一开始思路阻塞在，要根据奇偶性判断要取一个数还是2个数。并没有进一步的抽象，
    // 取一个和取两个可以用同一个函数完成，逻辑完全相同，而非自己找到第K个数后接着找第K+ 1个数
    // 接着找存在的问题，要分三种情况处理，跟找K个数一样，即在A中、在B中、在A or B中，徒增三个判断逻辑
    // 判断逻辑增多一是很容易出错，在这给自己增加了思维上的复杂性
    if (flag) {
        return GetKValue(nums1, nums1Size, nums2, nums2Size, num / 2 + 1);
    } else {
        return ((double)GetKValue(nums1, nums1Size, nums2, nums2Size, num / 2) + 
                (double)GetKValue(nums1, nums1Size, nums2, nums2Size, num / 2 + 1)) / 2;
    }
}

这位大佬的代码

下面是一开始自己的思路，根据b站的代码完善了一下：整体思路和我的差不多，不过这个逻辑清晰一点，自己的想的越来越复杂，陷入思维固化了，还有一个就是中位数，我想全面一点，但是这个就是只循环到一半，这样时间复杂度可以降到很少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int j=0,k=0;
    double preValue,currentvalue;
    int mid = (nums1Size+nums2Size)/2;

    for(int i=0;i<=mid;i++)
    {
        if(j < nums1Size && k < nums2Size)  //1 2都没走完
        {
            if(nums1[j] < nums2[k])
            {
                preValue = currentvalue;
                currentvalue = nums1[j];
                j++;
                continue;
            }else
            {
                preValue = currentvalue;
                currentvalue = nums2[k];
                k++;
                continue;
            }
        }
        if(k < nums2Size) //1走完 2没走完
        {
            preValue = currentvalue;
            currentvalue = nums2[k];
            k++;
            continue;
        }
        if(j < nums1Size)  //1没走完 2走完
        {
            preValue = currentvalue;
            currentvalue = nums1[j];
            j++;
            continue;
        }
    }
    if( (nums1Size+ nums2Size) % 2 ==0)
        return (preValue+currentvalue)/2;
    else
        return currentvalue;
}

真是一道题干半天。。。。。。思维爆炸！！！

更新于：2024年11月30日

LeetCode-C

字数：2.8k 字

时长：12 分钟

评论