[leetcode] 4. Median of Two Sorted Arrays
LeetCode of two sorted Arrays Median
2023-09-11 14:15:28 时间
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3] nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
-
在nums1里面二分下标,对每个下标对应的元素,计算其在nums2中最靠前能排到多少名,最靠后能排到多少名,主要是靠重复元素的存在。那么此元素在nums1里面的排名加上其在nums2里面的排名区间,即可判断此元素是否就是中位数。
-
还需要假设此元素在nums2中
-
需要考虑合并后的长度是奇数还是偶数
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 double bsearch(vector<int>& nums1, vector<int>& nums2, int pos) { 5 int low = 0,high = nums1.size()-1, tar = -1; 6 while(low <= high) { 7 int mid = (low + high) >> 1; 8 int val = nums1[mid]; 9 int x = lower_bound(nums2.begin(),nums2.end(),val) - nums2.begin(); 10 int y = upper_bound(nums2.begin(), nums2.end(),val) - nums2.begin(); 11 if (mid + x <= pos and pos <= mid + y) { 12 tar = nums1[mid]; 13 break; 14 } else if (mid + x > pos) high = mid - 1; 15 else low = mid + 1; 16 } 17 return tar; 18 } 19 20 21 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 22 int tlen = nums1.size() + nums2.size(); 23 double ret = 0; 24 25 int pos = tlen>>1; 26 ret = bsearch(nums1, nums2, pos); 27 if (ret == -1) ret = bsearch(nums2, nums1, pos); 28 29 if ((tlen&1) == 0) { 30 pos = (tlen>>1)-1; 31 double tmp = bsearch(nums1, nums2, pos); 32 if (tmp == -1) tmp = bsearch(nums2, nums1, pos); 33 ret += tmp; 34 ret *= 0.5; 35 } 36 37 return ret; 38 39 } 40 41 42 43 int main() { 44 vector<int>a = {1,2}; 45 vector<int>b = {3,4}; 46 cout<<findMedianSortedArrays(a,b)<<endl; 47 return 0; 48 }
相关文章
- Leetcode: Find Leaves of Binary Tree
- Leetcode: Sum of Two Integers && Summary: Bit Manipulation
- Leetcode: Intersection of Two Arrays II
- Leetcode: Intersection of Two Arrays
- Leetcode: Count of Smaller Numbers After Self
- Leetcode: Power of Two
- Leetcode: Median of Two Sorted Arrays
- Leetcode: Intersection of Two Linked Lists
- leetcode-38 Count And Say
- 【Leetcode】53. 最大子数组和(简单)
- [LeetCode] Intersection of Two Linked Lists
- [LeetCode] Search in Rotated Sorted Array II
- [LeetCode] Gas Station
- [LeetCode] 1297. Maximum Number of Occurrences of a Substring 子串的最大出现次数
- [LeetCode] 1295. Find Numbers with Even Number of Digits 统计位数为偶数的数字
- [LeetCode] 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold 元素和小于等于阈值的正方形的最大边长
- [LeetCode] 1254. Number of Closed Islands 统计封闭岛屿的数目
- [LeetCode] 990. Satisfiability of Equality Equations 等式方程的可满足性
- [LeetCode] 977. Squares of a Sorted Array 有序数组的平方值
- [LeetCode] Cherry Pickup 捡樱桃
- [LeetCode] Single Element in a Sorted Array 有序数组中的单独元素
- [LeetCode] Exclusive Time of Functions 函数的独家时间
- [LeetCode] Find the Derangement of An Array 找数组的错排
- [LeetCode] 421. Maximum XOR of Two Numbers in an Array 数组中异或值最大的两个数字
- [LeetCode] 363. Max Sum of Rectangle No Larger Than K 最大矩阵和不超过K
- [LeetCode] 305. Number of Islands II 岛屿的数量之二
- [LeetCode] Number of Connected Components in an Undirected Graph 无向图中的连通区域的个数
- [LeetCode] Power of Two 判断2的次方数
- [LeetCode] Number of 1 Bits 位1的个数
- Leetcode——4. Median of Two Sorted Arrays
- leetcode 191. Number of 1 Bits 位1的个数(简单)
- leetcode 4. Median of Two Sorted Arrays 寻找两个正序数组的中位数(困难)