0%

leetcode 中位数

力扣4+88题,寻找两个有序数组的中位数

皮卡丘

88题,合并两个有序数组

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
/*
* @lc app=leetcode.cn id=88 lang=java
*
* [88] 合并两个有序数组
*/
//双指针
// @lc code=start
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
/**
* 最简单方法就是合并后排序
* System.arraycopy(num2, 0, num1, m, n);
* Arrays.sort(num1);
*/
//把num1的数放在其他地方,num1用来存放结果
int[] num1_copy = new int[m];
System.arraycopy(nums1, 0, num1_copy, 0, m);
int p1 = 0, p2 = 0;//num1_copy和num2的指针
int p =0;//num1的指针
while((p1 < m) && (p2 < n)){
nums1[p++] = (num1_copy[p1] < nums2[p2]) ? num1_copy[p1++] : nums2[p2++];
//若还剩下一个数组没用用完
}
if(p1 < m){
System.arraycopy(num1_copy, p1, nums1, p1+p2, m-p1);
}
if(p2 < n){
System.arraycopy(nums2, p2, nums1, p1+p2, n-p2);
}
}
}
// @lc code=end

4题,寻找中位数

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
/*
* @lc app=leetcode.cn id=4 lang=java
*
* [4] 寻找两个正序数组的中位数
*/
/**
* 时间复杂度要求log(m+n),则用二分查找
*
*/
// @lc code=start
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if(nums1.length > nums2.length){
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length;
int n = nums2.length;

//分割线左边的所有元素需要满足的个数
int totalLeft = (m + n + 1) / 2;

//在num1的区间[0,m]里查找恰当的分割线
//使得 num1[i-1]<=num2[j]&&num1[i]>=num2[j-1]
int left = 0;
int right = m;
while(left < right){
int i = left + (right - left + 1)/2;
int j =totalLeft - i;
if(nums1[i-1] > nums2[j]){
//搜索区间[left,i-1]
right = i - 1;
}else{
//[i , right]
left = i;
}
}
int i = left;
int j = totalLeft - i;

//分割线左右的四个值
int num1LeftMax = ((i == 0) ? Integer.MIN_VALUE : nums1[i-1]);
int num1RightMin = ((i == m) ? Integer.MAX_VALUE : nums1[i]);
int num2LeftMax = ((j == 0) ? Integer.MIN_VALUE : nums2[j-1]);
int num2RightMin = ((j == n) ? Integer.MAX_VALUE : nums2[j]);

if((m + n) % 2 == 1){
return Math.max(num1LeftMax, num2LeftMax);
}else{
return (double) ((Math.max(num1LeftMax, num2LeftMax) + Math.min(num1RightMin, num2RightMin))) / 2;
}
}
}
// @lc code=end
-------------本文结束感谢您的阅读-------------