Binary-Search

题目要求Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.Note:You may assume the interval's end point is always bigger than its start point.You may assume none of these intervals have the same start point. Example 1:Input: [ [1,2] ]Output: [-1]Explanation: There is only one interval in the collection, so it outputs -1. Example 2:Input: [ [3,4], [2,3], [1,2] ]Output: [-1, 0, 1]Explanation: There is no satisfied "right" interval for [3,4].For [2,3], the interval [3,4] has minimum-"right" start point;For [1,2], the interval [2,3] has minimum-"right" start point. Example 3:Input: [ [1,4], [2,3], [3,4] ]Output: [-1, 2, -1]Explanation: There is no satisfied "right" interval for [1,4] and [3,4].For [2,3], the interval [3,4] has minimum-"right" start point.NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.假设一个二维的整数数组中每一行表示一个区间，每一行的第一个值表示区间的左边界，第二个值表示区间的右边界。现在要求返回一个整数数组，用来记录每一个边界右侧最邻近的区间。 ...

题目要求Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.Example:Input: matrix = [[1,0,1],[0,-2,3]], k = 2Output: 2 Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).Note:1. The rectangle inside the matrix must have an area > 0.2. What if the number of rows is much larger than the number of columns?现有一个由整数构成的矩阵，问从中找到一个子矩阵，要求该子矩阵中各个元素的和为不超过k的最大值，问子矩阵中元素的和为多少?注：后面的文章中将使用[左上角顶点坐标，右下角顶点坐标]来表示一个矩阵，如[(1,2),(3,4)]表示左上角顶掉坐标为(1,2)，右下角顶点坐标为(3,4)的矩阵。用S[(1,2),(3,4)]表示该矩阵的面积。顶点的坐标系以数组的起始点作为起点，向下为x轴正方向，向右为y轴正方向。 ...

题目要求Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.Note:If n is the length of array, assume the following constraints are satisfied:1 ≤ n ≤ 10001 ≤ m ≤ min(50, n)Examples:Input:nums = [7,2,5,10,8]m = 2Output:18Explanation:There are four ways to split nums into two subarrays.The best way is to split it into [7,2,5] and [10,8],where the largest sum among the two subarrays is only 18.将一个长度为n的正整数数组分割为m个非空的连续子数组，并分别计算每个子数组中所有元素的和。求一种分割方式，使得该分割方式生成的最大子数组和为所有分割方式中最小的。 ...

题目要求Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.Note that it is the kth smallest element in the sorted order, not the kth distinct element.Example:matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15]],k = 8,return 13.Note: You may assume k is always valid, 1 ≤ k ≤ n2.在一个从左到右，从上到下均有序的二维数组中，找到从小到第k个数字，这里需要注意，不要求一定要是唯一的值，即假设存在这样一个序列1,2,2,3，则第三个数字是2而不是3。思路一：优先队列当涉及到从一个集合中查找一个元素这样的问题时，我们往往会立刻想到查找的几种方式：有序数组查找，无序数组查找，堆排序。这里如果将二维数组转化为一维有序数组，成本未免太大了。同理，将其中所有元素都转化为堆，也会存在内存不足的问题。因此我们可以采用部分元素堆排序即可。即我们每次只需要可能构成第k个元素的值进行堆排序就可以了。 public int kthSmallest(int[][] matrix, int k) { //优先队列 PriorityQueue<Tuple> queue = new PriorityQueue<Tuple>(); //将每一行的第一个元素放入优先队列中 for(int i = 0 ; i<matrix.length ; i++) { queue.offer(new Tuple(i, 0, matrix[i][0])); } //对优先队列执行k次取操作，取出来的就是第k个值 for(int i = 0 ; i<k-1 ; i++) { Tuple t = queue.poll(); //判断是否到达行尾，若没有，则将下一个元素作为潜在的第k个元素加入优先队列中 if(t.y == matrix[0].length-1) continue; queue.offer(new Tuple(t.x, t.y+1, matrix[t.x][t.y+1])); } return queue.poll().value; } /** * 存储矩阵中x，y和该下标上对应的值的Tuple */ public static class Tuple implements Comparable<Tuple>{ int x; int y; int value; public Tuple(int x, int y, int value) { this.x = x; this.y = y; this.value = value; } @Override public int compareTo(Tuple o) { // TODO Auto-generated method stub return this.value - o.value; } }思路二：二分法查找二分查找的核心问题在于，如何找到查找的上界和下届。这边我们可以矩阵中的最大值和最小值作为上界和下界。然后不停的与中间值进行比较，判断当前矩阵中小于该中间值的元素有几个，如果数量不足k，就将左指针右移，否则，就将右指针左移。直到左右指针相遇。这里需要注意，不能在数量等于k的时候就返回mid值，因为mid值不一定在矩阵中存在。 public int kthSmallest2(int[][] matrix, int k){ int low = matrix[0][0], high = matrix[matrix.length-1][matrix[0].length-1]; while(low <= high) { int mid = low + (high - low) / 2; int count = 0; int i = matrix.length-1 , j = 0; //自矩阵左下角开始计算比mid小的数字的个数 while(i>=0 && j < matrix.length){ if(matrix[i][j]>mid) i–; else{ count+=i+1; j++; } } if(count < k) { low = mid + 1; }else{ high = mid - 1; } } return low; } ...

ProblemGiven an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.Note:If n is the length of array, assume the following constraints are satisfied:1 ≤ n ≤ 10001 ≤ m ≤ min(50, n)Examples:Input:nums = [7,2,5,10,8]m = 2Output:18Explanation:There are four ways to split nums into two subarrays.The best way is to split it into [7,2,5] and [10,8],where the largest sum among the two subarrays is only 18.Solutionclass Solution { public int splitArray(int[] nums, int m) { long sum = 0L, max = 0L; for (int num: nums) { sum += (long) num; max = (long) Math.max(max, num); } if (m == 1) return (int) sum; long l = max, r = sum; while (l <= r) { long mid = l + (r-l)/2; if (valid(nums, mid, m)) r = mid-1; else l = mid+1; } return (int) l; } private boolean valid(int[] nums, long target, int m) { int count = 1; long sum = 0L; for (int num: nums) { sum += num; if (sum > target) { count++; sum = num; if (count > m) return false; } } return true; }} ...

ProblemGiven an integer array sorted in ascending order, write a function to search target in nums. If target exists, then return its index, otherwise return -1. However, the array size is unknown to you. You may only access the array using an ArrayReader interface, where ArrayReader.get(k) returns the element of the array at index k (0-indexed).You may assume all integers in the array are less than 10000, and if you access the array out of bounds, ArrayReader.get will return 2147483647.Example 1:Input: array = [-1,0,3,5,9,12], target = 9Output: 4Explanation: 9 exists in nums and its index is 4Example 2:Input: array = [-1,0,3,5,9,12], target = 2Output: -1Explanation: 2 does not exist in nums so return -1Note:You may assume that all elements in the array are unique.The value of each element in the array will be in the range [-9999, 9999].Solutionclass Solution { public int search(ArrayReader reader, int target) { //find higher bound int r = 1; while (reader.get(r) < target) r *= 2; //then you know lower bound int l = r/2; while (l <= r) { int m = l+(r-l)/2; if (reader.get(m) == target) return m; else if (reader.get(m) < target) l = m+1; else r = m-1; } return -1; }} ...