Leetcode刷题 2020.7.17

2023-12-16 07:08

文章标签 leetcode 刷题 17 2020.7

本文主要是介绍Leetcode刷题 2020.7.17，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

寻找两个正序数组中的中位数
注意边界的判断：
[2]
[]
这个样例

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int len1 = nums1.size(), len2 = nums2.size(), kk, ans;double t;if((len1 + len2)%2) kk = (len1 + len2)/2;else kk = (len1 + len2 - 1)/2;for (int i = 0, j = 0, k = 0; i <= kk; i++){if(j < len1 && k < len2)   //核心判断！！！！[2][]if(nums1[j] <= nums2[k]) ans = nums1[j++];else ans = nums2[k++];else if(j < len1) ans = nums1[j++];else ans = nums2[k++];if(i == kk && (len1 + len2)%2 == 0){int p;if(j < len1 && k < len2) p = min(nums1[j], nums2[k]);else if(j < len1) p = nums1[j];else p = nums2[k];return (ans + p)/2.0;}}return 1.0*ans;}
};

网上借鉴的写法，通过将边界情况作成正负无穷，来避免冗杂的边界判断。


class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {if(nums1.size() > nums2.size()) swap(nums1, nums2);int m = nums1.size(), n = nums2.size();int l = 0, r = m, i, j, a, b, c, d, M1, M2;while(l <= r){i = (l + r) >> 1;j = (m + n + 1)/2 - i; a = i == 0 ? INT_MIN : nums1[i - 1];b = i == m ? INT_MAX : nums1[i];c = j == 0 ? INT_MIN : nums2[j - 1];d = j == n ? INT_MAX : nums2[j];if(a <= d){M1 = max(a, c);M2 = min(b, d);l = i + 1;}else r = i - 1;}return (m + n)%2 ? 1.0*M1 : (M1 + M2)/2.0;}};

错误代码，待修改。


class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size(), n = nums2.size();if(m > n) swap(nums1, nums2), swap(m, n);// 偶数: i + j = n - i + m - j// 奇数: i + j = n - i + m - j + 1// j = (n + m)/2 - i  -----> j = (n + m + 1)/2 -i// j = (n + m + 1)/2 - iint i, j;  //(两个数组的一般半长度 - i)如果这个值合法//合法即满足 0 <= j < n, 则 i 必须小于整个数组一半长度，所以i 必须来自短数组int l = 0, r = m, M1, M2;while(l <= r){ i = (l + r)/2;j = (n + m + 1)/2 - i;if(i > 0 && i <= m) {if(i == m){M1 = max(nums1[i - 1], nums2[j - 1]);M2 = nums2[j];break;}if(nums1[i - 1] <= nums2[j]) {M1 = max(nums1[i - 1], nums2[j - 1]);M2 = min(nums1[i], nums2[j]);l = i + 1;}else r = i - 1;}else{if(!i){if(!m) {M1 = M2 = nums2[j - 1];if(j < n) M2 = nums2[j];}else {if(j > 1 && nums1[0] <= nums2[j - 2]){M1 = M2 = nums2[j - 2];if(j < n) M2 = nums2[j - 1];}else if(j == 1 && nums1[0] <= nums2[j - 1]){M1 = M2 = nums2[0];if(j < n) M2 = nums2[j - 1];}else{M1 = M2 = min(nums1[0], nums2[j]);if(j < n) M2 = max(nums1[0], nums2[j]);}}}break;}}return (n + m)%2 ? 1.0*M1 : 1.0*(M1 + M2)/2.0;}};