leeyupeng

leeyupeng@126.com

0%

两个有序数组的第K小元素问题

发表于 分类于 ， 阅读次数： Valine：

两个有序数组的第K小元素问题

问题描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的第K小的元素，并且要求算法的时间复杂度为 O(log(m + n))。

归并法

思路分析

将两个有序数组归并为一个有序数组

代码实现

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
int findKSortedArraysMerge(vector<int>& nums1, vector<int>& nums2,int k)
{
	int m = nums1.size();
	int n = nums2.size();
	vector<int> nums(m + n);
	int i = 0, j = 0;
	for (int kk = 0; kk < m+n; kk++)
	{
		if (i == m)
		{
			nums[kk] = nums2[j];
			j++;
		}
		else if (j == n)
		{
			nums[kk] = nums1[i];
			i++;
		}
		else if(nums1[i] <= nums2[j])
		{
			nums[kk] = nums1[i];
			i++;
		}
		else
		{
			nums[kk] = nums2[j];
			j++;
		}
	}
	return nums[k - 1];
}

双指针

  • i=0,j=0起始 0<=i<=m,0<=j<=n
  • A[i]<B[j] i++
  • A[i]>B[j] j++
  • i + j = k 停止
  • ans = max(A[i-1],B[j-1])

思路分析

代码实现

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
int findKSortedArraysIJ(vector<int>& nums1, vector<int>& nums2,int k)
{
  int i = 0, j = 0;
  int m = nums1.size();
  int n = nums2.size();
  while (i + j < k)
  {
    if (i == m)
    {
      j++;
    }
    else if (j == n)
    {
      i++;
    }
    else if(nums1[i] <= nums2[j])
    {
      i++;
    }
    else
    {
      j++;
    }
  }

  int max_left = 0;
  if (i == 0)
  {
    max_left = nums2[j - 1];
  }
  else if (j == 0)
  {
    max_left = nums1[i - 1];
  }
  else
  {
    max_left = nums1[i - 1] > nums2[j - 1] ? nums1[i - 1] : nums2[j - 1];
  }
  return max_left;
}

二分法

思路分析

  • 1.假设中位数的位置在 A B 数组的 i,j位置 0<=i<=m,0<=j<=n
    则满足：
    • 1.i+j = k
    • 2.集合A(0,i-1)和集合B(0,j-1) 小于 集合A(i,m-1)和集合B(j,n-1)
  • 2.临界处理
    • 1.数组为空
    • 2.i==0 j==0 i==m j==n

代码实现

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
int findKSortedArraysBisection(vector<int>& nums1, vector<int>& nums2,int k)
{
  int m = nums1.size();
  int n = nums2.size();
  int i = 0;
  int j = k - i;
  int iMin = 0, iMax = m;
  if (m == 0)
  {
    i = 0;
    j = k;
  }
  else if (n == 0)
  {
    i = k;
    j = 0;
  }
  else
  {
    while (iMin <= iMax)
    {
      i = (iMin + iMax) / 2;
      j = k - i;

      if (j < 0)
      {
        iMax = i - 1;
        continue;
      }
      else if (j > n)
      {
        iMin = i + 1;
        continue;
      }

      if (i == m)
      {
        if (nums1[i - 1] <= nums2[j])
        {
          break;
        }
        else
        {
          iMax = i - 1;
          continue;
        }
      }
      else if (i == 0)
      {
        if (nums1[i] >= nums2[j - 1])
        {
          break;
        }
        else
        {
          iMin = i + 1;
          continue;
        }
      }

      if (j == n)
      {
        if (nums1[i] >= nums2[j - 1])
        {
          break;
        }
        else
        {
          iMin = i + 1;
          continue;
        }
      }
      else if (j == 0)
      {
        if (nums1[i - 1] <= nums2[j])
        {
          break;
        }
        else
        {
          iMax = i - 1;
          continue;
        }
      }
      if (nums1[i - 1] > nums2[j])
      {
        iMax = i - 1;
      }
      else if (nums1[i] < nums2[j - 1])
      {
        iMin = i + 1;
      }
      else
      {
        break;
      }
    }
  }

  int max_left = 0;
  if (i == 0)
  {
    max_left = nums2[j - 1];
  }
  else if (j == 0)
  {
    max_left = nums1[i - 1];
  }
  else
  {
    max_left = nums1[i - 1] > nums2[j - 1] ? nums1[i - 1] : nums2[j - 1];
  }
  return max_left;
}

寻找两个有序数组的中位数

问题描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

leetcode4.寻找两个有序数组的中位数