区块链技术博客
www.b2bchain.cn

单个或俩个有序数组中位数

这篇文章主要介绍了单个或俩个有序数组中位数,通过具体代码讲解8079并且分析了单个或俩个有序数组中位数的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了单个或俩个有序数组中位数。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/8079.html。具体如下:

剑指 Offer 41. 数据流中的中位数   堆来实现 大堆存小部分  小堆存大部分

 //中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。  // // 例如,  // // [2,3,4] 的中位数是 3  // // [2,3] 的中位数是 (2 + 3) / 2 = 2.5  // // 设计一个支持以下两种操作的数据结构:  // //  // void addNum(int num) - 从数据流中添加一个整数到数据结构中。  // double findMedian() - 返回目前所有元素的中位数。  //  // // 示例:  // // addNum(1) //addNum(2) //findMedian() -> 1.5 //addNum(3)  //findMedian() -> 2  // // 进阶:  // //  // 如果数据流中所有整数都在 0 到 100 范围内,你将如何优化你的算法?  // 如果数据流中 99% 的整数都在 0 到 100 范围内,你将如何优化你的算法?  //  // Related Topics 堆 设计   import java.util.PriorityQueue;  //leetcode submit region begin(Prohibit modification and deletion) class MedianFinder {     PriorityQueue<Integer> heapA;     PriorityQueue<Integer> heapB;      /** initialize your data structure here. */     public MedianFinder() {         heapA=new PriorityQueue<>();         heapB=new PriorityQueue<>((v1,v2)->v2-v1);     }     //小顶堆 存较大部分   大顶堆存较小部分     public void addNum(int num) {         if(heapA.size()!=heapB.size()){             heapB.add(num);             heapA.add(heapB.poll());         }         else{             heapA.add(num);             heapB.add(heapA.poll());         }      }          public double findMedian() {        if(heapA.size()!=heapB.size()) return heapB.peek();        else return (heapA.peek()+heapB.peek())/2.0;     } }  /**  * Your MedianFinder object will be instantiated and called as such:  * MedianFinder obj = new MedianFinder();  * obj.addNum(num);  * double param_2 = obj.findMedian();  */ //leetcode submit region end(Prohibit modification and deletion) 

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

 public 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;          // 分割线左边的所有元素需要满足的个数 m + (n - m + 1) / 2;         int totalLeft = (m + n + 1) / 2;          // 在 nums1 的区间 [0, m] 里查找恰当的分割线,         // 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]         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 nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];         int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];         int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];         int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];          if (((m + n) % 2) == 1) {             return Math.max(nums1LeftMax, nums2LeftMax);         } else {             return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;         }     } } 

 

本文地址https://www.b2bchain.cn/8079.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 单个或俩个有序数组中位数
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们