当前位置：首页 > news >正文

java学习 leetcode 二分查找图论

news 2025/8/15 15:32:24

74 搜索二维矩阵

class Solution {public boolean searchMatrix(int[][] matrix, int target) {if(matrix == null || matrix.length == 0 || matrix[0].length == 0){return false;}int m = matrix.length;int n = matrix[0].length;int left = 0;int right = m*n -1;while(left <= right){int mid = left + (right -left)/2;int midvalue = matrix[mid/n][mid%n];if(midvalue == target){return true;}else if(midvalue < target){left =mid +1;}else{right = mid -1;}}return false;}
}

34 排序数组查找第一个最后一个位置

旋转排序数组、以及最小值，这类思路差不多

4. 寻找正序数组的中位数

这个比较难写，后面再看看，思路是：一个是划分数组，一个二分查找

// class Solution {
//     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
//         //思路就是找到索引为 ,,这里的代码可能后面完善下
//         //(m + n) / 2  -> (m+n)/2+1的平均值
//         //奇数的话找到 (m + n)/2
//         int right_m = m = nums1.length;
//         int right_n = n = nums2.length;
//         int left_m = left_n = 0;
//         int m_mid = m/2;
//         int n_mid = n/2;//         if(nums1[m_mid]>nums2[n_mid]){
//             left_n = n_mid;
//             while(nums2[left_n] < nums1[right_n]){//             }
//         }
//     }
// }class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {// 确保 nums1 是较短的数组，减少二分搜索范围if (nums1.length > nums2.length) {return findMedianSortedArrays(nums2, nums1);}int m = nums1.length;int n = nums2.length;int left = 0, right = m;  // 在 nums1 上进行二分while (left <= right) {int partition1 = left + (right - left) / 2;           // nums1 的分割线右边第一个元素的索引int partition2 = (m + n + 1) / 2 - partition1;        // nums2 的分割线// 左半部分的最大值int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];// 右半部分的最小值int minRight1 = (partition1 == m) ? Integer.MAX_VALUE : nums1[partition1];int minRight2 = (partition2 == n) ? Integer.MAX_VALUE : nums2[partition2];// 满足中位数分割条件：左 <= 右if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {// 分奇偶计算中位数if ((m + n) % 2 == 0) {// 偶数个元素：取 (左最大 + 右最小) / 2.0return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;} else {// 奇数个元素：左半部分最大值就是中位数return Math.max(maxLeft1, maxLeft2);}} else if (maxLeft1 > minRight2) {// nums1 分割线太靠右，需要左移right = partition1 - 1;} else {// maxLeft2 > minRight1，需要将 nums1 分割线右移left = partition1 + 1;}}// 理论上不会执行到这里throw new IllegalArgumentException("输入数组不是有序的");}
}