Tag Archives: 二分搜索

剑指 Offer 11. 旋转数组的最小数字

剑指 Offer 11. 旋转数组的最小数字剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。  

示例 1:

输入:[3,4,5,1,2]
输出:1
示例 2:

输入:[2,2,2,0,1]
输出:0
注意:本题与主站 154 题相同:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。剑指 Offer 11. 旋转数组的最小数字


LeetCode Find Minimum in Rotated Sorted Array II相同,即旋转有序数组中包含重复元素,求最小值。考虑nums[m]==nums[r]的情况,退化为线性查找,完整代码如下:

class Solution {
public:
	int minArray(vector<int>& numbers) {
		int n = numbers.size();
		int l = 0, r = n - 1;
        while(l <= r) {
            if(r - l <= 1) return min(numbers[l], numbers[r]);
            int m = l + (r - l) / 2;
            if(numbers[m] > numbers[r]) l = m;
            else if(numbers[m] == numbers[r]) --r;
            else r = m;
        }
		return 0;
	}
};

本代码提交AC,用时12MS。

剑指 Offer 04. 二维数组中的查找

剑指 Offer 04. 二维数组中的查找

在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下:

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5,返回 true。

给定 target = 20,返回 false。

限制:

0 <= n <= 1000

0 <= m <= 1000

注意:本题与主站 240 题相同:https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定一个矩阵,每行从左到右升序排列,每列从上到下升序排列,给定一个数,问这个数在不在矩阵中。

从矩阵右上角开始查找,代码如下:

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;
        int n = matrix.size(), m = matrix[0].size();
        int i = 0, j = m - 1;
        while(i < n && j >= 0) {
            if(matrix[i][j] == target) return true;
            if(target > matrix[i][j]) ++i;
            else --j;
        }
        return false;
    }
};

本代码提交AC,用时64MS。

LeetCode Minimum Number of Days to Make m Bouquets

5455. Minimum Number of Days to Make m Bouquets

Given an integer array bloomDay, an integer m and an integer k.

We need to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.

The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.

Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

Example 1:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

Example 2:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.

Example 3:

Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
Explanation: We need 2 bouquets each should have 3 flowers.
Here's the garden after the 7 and 12 days:
After day 7: [x, x, x, x, _, x, x]
We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.
After day 12: [x, x, x, x, x, x, x]
It is obvious that we can make two bouquets in different ways.

Example 4:

Input: bloomDay = [1000000000,1000000000], m = 1, k = 1
Output: 1000000000
Explanation: You need to wait 1000000000 days to have a flower ready for a bouquet.

Example 5:

Input: bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
Output: 9

Constraints:

  • bloomDay.length == n
  • 1 <= n <= 10^5
  • 1 <= bloomDay[i] <= 10^9
  • 1 <= m <= 10^6
  • 1 <= k <= n

花园里有n朵花,告诉你每朵花在第几天开花。现在要扎m束花,每束花必须由相邻的k朵花组成,问要完成这个任务,最少需要等多少天。

首先看看需要的总花数m*k是否>n,如果是的话,即使所有花都开了也无法完成任务。

对于能够完成的任务,要求最少等待天数。暴力方法是,枚举bloomDay数组中所有unique的天数,对于每一天,都看看能否完成任务,方法是把数组中相邻的开的花每k多组成一束,看看能否组成m束。

但是暴力方法超时,一个改进的方法是二分。因为天数是递增的,而且每增加一天,开花的总数也是递增的,相当于能组成的花束也是递增的(严格来说是非递减的),这就为二分搜索创造了条件。

维护两个数组,days存储了unique的天数,递增排序(map自动递增有序了);num_bloomed表示在当前天数下,开花的总数,随着days的增大, num_bloomed 存储的开花总数也是递增的。在构造 num_bloomed 的过程中,可以求到最小的可能的开始天数left,然后在left和right中二分搜索合法的最小天数。

完整代码如下:

class Solution {
	bool IsValid(vector<int>& bloomDay, int day, int m, int k) {
		int bouquets = 0, n = bloomDay.size();
		int i = 0, good = 0;
		while (i < n) {
			while (i<n&&bloomDay[i]>day)++i;
			if (i >= n)break;

			int j = i;
			while (j < n&&bloomDay[j] <= day)++j;
			// [i,j) 都开花了

			good += (j - i) / k;

			i = j;
		}
		return good >= m;
	}
public:
	int minDays(vector<int>& bloomDay, int m, int k) {
		int n = bloomDay.size();
		if (m*k > n)return -1;

		map<int, int> hash;
		for (int i = 0; i < n; ++i)++hash[bloomDay[i]];
		if (m*k == n)return (--hash.end())->first; // 最后一天

		int unique_day = hash.size();
		vector<int> days(unique_day, 0);
		vector<int> num_bloomed(unique_day, 0);

		int d = 0, nb = 0;
		int left = 0, right = unique_day - 1, found_left = false;
		for (map<int, int>::iterator it = hash.begin(); it != hash.end(); ++it) {
			nb += it->second;
			if (nb >= m * k && !found_left) {
				left = d;
				found_left = true;
			}

			days[d] = it->first;
			num_bloomed[d] = nb;
			
			++d;
		}

		while (left <= right) {
			int mid = left + (right - left) / 2;
			bool valid = IsValid(bloomDay, days[mid], m, k);
			if (valid)right = mid - 1;
			else left = mid + 1;
		}

		return days[right + 1];
	}
};

本代码提交AC,用时1316MS。

LeetCode Leftmost Column with at Least a One

LeetCode Leftmost Column with at Least a One

(This problem is an interactive problem.)

A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn’t exist, return -1.

You can’t access the Binary Matrix directly.  You may only access the matrix using a BinaryMatrix interface:

  • BinaryMatrix.get(x, y) returns the element of the matrix at index (x, y) (0-indexed).
  • BinaryMatrix.dimensions() returns a list of 2 elements [m, n], which means the matrix is m * n.

Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer.  Also, any solutions that attempt to circumvent the judge will result in disqualification.

For custom testing purposes you’re given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.

Example 1:

Input: mat = [[0,0],[1,1]]
Output: 0

Example 2:

Input: mat = [[0,0],[0,1]]
Output: 1

Example 3:

Input: mat = [[0,0],[0,0]]
Output: -1

Example 4:

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 100
  • mat[i][j] is either 0 or 1.
  • mat[i] is sorted in a non-decreasing way.

给定一个0/1矩阵,且每行是升序排列的。问矩阵中至少包含一个1的列的最小列号。要求不能使用访问矩阵超过1k次,矩阵最大是100*100的。

常规解法。由于矩阵每行有序,所以在每一行中,使用二分搜索的方式找到1的最小下标,则所有行的最小下标的最小值即为答案。如果是m*n的矩阵,则时间复杂度为O(mlgn)。代码如下:

class Solution {
public:
	int LeftMost(BinaryMatrix &binaryMatrix, int row, int m, int n) {
		int l = 0, r = n - 1;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			int midv = binaryMatrix.get(row, mid);
			if (midv == 0)l = mid + 1;
			else r = mid - 1;
		}
		return r + 1;
	}
	int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
		vector<int> dim = binaryMatrix.dimensions();
		int m = dim[0], n = dim[1];
		int ans = n;
		for (int i = 0; i < m; ++i) {
			ans = min(ans, LeftMost(binaryMatrix, i, m, n));
		}
		if (ans == n)return -1;
		else return ans;
	}
};

本代码提交AC,用时8MS。

hint还提示了另一种解法,从矩阵的右上角开始,遇到0则往下走,遇到1则往左走。因为如果是1的话,至少当前所在列是包含1的,也许还可以再往左试探一下,而如果是0的话,只能往下走了。这种方法极端情况下可能从矩阵的右上角走到左下角,时间复杂度为O(m+n)。完整代码如下:

class Solution {
public:

	int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
		vector<int> dim = binaryMatrix.dimensions();
		int m = dim[0], n = dim[1];
		int x = 0, y = n - 1;
		int ans = n;
		while (x < m&&y >= 0) {
			int val = binaryMatrix.get(x, y);
			if (val == 0)++x;
			else if (val == 1) {
				ans = y;
				if (y - 1 >= 0 && binaryMatrix.get(x, y - 1) == 1) {
					--y;
					ans = y;
				}
				else ++x;
			}
		}
		if (ans == n)return -1;
		else return ans;
	}
};

本代码提交AC,用时8MS。

LCP 08. 剧情触发时间

LCP 08. 剧情触发时间

在战略游戏中,玩家往往需要发展自己的势力来触发各种新的剧情。一个势力的主要属性有三种,分别是文明等级(C),资源储备(R)以及人口数量(H)。在游戏开始时(第 0 天),三种属性的值均为 0。

随着游戏进程的进行,每一天玩家的三种属性都会对应增加,我们用一个二维数组 increase 来表示每天的增加情况。这个二维数组的每个元素是一个长度为 3 的一维数组,例如 [[1,2,1],[3,4,2]] 表示第一天三种属性分别增加 1,2,1 而第二天分别增加 3,4,2

所有剧情的触发条件也用一个二维数组 requirements 表示。这个二维数组的每个元素是一个长度为 3 的一维数组,对于某个剧情的触发条件 c[i], r[i], h[i],如果当前 C >= c[i] 且 R >= r[i] 且 H >= h[i] ,则剧情会被触发。

根据所给信息,请计算每个剧情的触发时间,并以一个数组返回。如果某个剧情不会被触发,则该剧情对应的触发时间为 -1 。

示例 1:

输入: increase = [[2,8,4],[2,5,0],[10,9,8]] requirements = [[2,11,3],[15,10,7],[9,17,12],[8,1,14]]

输出: [2,-1,3,-1]

解释:

初始时,C = 0,R = 0,H = 0

第 1 天,C = 2,R = 8,H = 4

第 2 天,C = 4,R = 13,H = 4,此时触发剧情 0

第 3 天,C = 14,R = 22,H = 12,此时触发剧情 2

剧情 1 和 3 无法触发。

示例 2:

输入: increase = [[0,4,5],[4,8,8],[8,6,1],[10,10,0]] requirements = [[12,11,16],[20,2,6],[9,2,6],[10,18,3],[8,14,9]]

输出: [-1,4,3,3,3]

示例 3:

输入: increase = [[1,1,1]] requirements = [[0,0,0]]

输出: [0]

限制:

  • 1 <= increase.length <= 10000
  • 1 <= requirements.length <= 100000
  • 0 <= increase[i] <= 10
  • 0 <= requirements[i] <= 100000

玩家有c,r,h三个值,每过一天三个值有不同程度的增加,问满足不同阈值的最小天数。

暴力方法两层循环会超时。可以先分别构建c,r,h的递增数组,然后针对每个requirement,在递增数组中二分查找满足阈值的左边界,三个左边界的最大值即为满足3个条件的最小天数。

完整代码如下:

class Solution {
public:
	vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {
		int m = increase.size(), n = requirements.size();
		vector<int> cs(m + 1, 0), rs(m + 1, 0), hs(m + 1, 0);

		for (int i = 0; i < m; ++i) {
			cs[i + 1] = cs[i] + increase[i][0];
			rs[i + 1] = rs[i] + increase[i][1];
			hs[i + 1] = hs[i] + increase[i][2];
		}

		vector<int> ans(n, -1);

		for (int i = 0; i < n; ++i) {
			int minc = lower_bound(cs.begin(), cs.end(), requirements[i][0]) - cs.begin();
			int minr = lower_bound(rs.begin(), rs.end(), requirements[i][1]) - rs.begin();
			int minh = lower_bound(hs.begin(), hs.end(), requirements[i][2]) - hs.begin();
			int cur = max(max(minc, minr), minh);
			if (cur <= m)ans[i] = cur;
		}


		return ans;
	}
};

本代码提交AC,用时988MS。

LeetCode Find First and Last Position of Element in Sorted Array

34. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

给定一个有序数组,里面可能有重复元素,要求找出某个元素所有出现位置的起始位置和终止位置。

由于是有序数组,所以直接二分搜索,需要注意的是如果是找起始位置,则找到目标元素后还应该继续往左找,可以想象mid一直遇到target,则要不断执行r=mid-1,直到退出while循环,此时老的mid是等于target的最小下标,所以要返回r+1。类似的,如果找终止位置,则遇到相等后还要继续往右找,即l=mid+1,失败的时候返回上一个mid,即l-1。

完整代码如下:

class Solution {
public:
	int FindFirstIndex(vector<int>& nums, int target) {
		int l = 0, r = nums.size() - 1;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (target <= nums[mid])r = mid - 1;
			else l = mid + 1;
		}
		if (r + 1 < nums.size() && nums[r + 1] == target)return r + 1;
		else return -1;
	}
	int FindLastIndex(vector<int>& nums, int target) {
		int l = 0, r = nums.size() - 1;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (target >= nums[mid])l = mid + 1;
			else r = mid - 1;
		}
		if (l - 1 >= 0 && nums[l - 1] == target)return l - 1;
		else return -1;
	}
	vector<int> searchRange(vector<int>& nums, int target) {
		return { FindFirstIndex(nums,target),FindLastIndex(nums,target) };
	}
};

本代码提交AC,用时4MS。

LeetCode Find K Closest Elements

LeetCode Find K Closest Elements Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred. Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]
Example 2:
Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]
Note:
  1. The value k is positive and will always be smaller than the length of the sorted array.
  2. Length of the given array is positive and will not exceed 104
  3. Absolute value of elements in the array and x will not exceed 104

给定一个有序数组,要从中找出k个和x最接近的元素,按升序排列输出。 首先在有序数组中用二分查找找到x的lowerbound,如果lowerbound指向begin(),则取开头k个元素即可;如果lowerbound指向end(),则取末尾k个元素;否则,令left指向lowerbound-1,right指向lowerbound,每次取left、right中和x差值最小的那个数,直到取够k个为止。最后对结果数组排序。 完整代码如下: [cpp] class Solution { public: vector<int> findClosestElements(vector<int>& arr, int k, int x) { vector<int> ans; int n = arr.size(); auto it = lower_bound(arr.begin(), arr.end(), x); if (it == arr.begin()) { while (ans.size() < k) { ans.push_back(*it++); } return ans; } else if (it == arr.end()) { while (ans.size() < k) { ans.push_back(*–it); } return ans; } else { int right = it – arr.begin(); int left = right – 1; int left_diff = INT_MAX, right_diff = INT_MAX; while (ans.size() < k) { if (left >= 0)left_diff = abs(arr[left] – x); else left_diff = INT_MAX; if (right < n)right_diff = abs(arr[right] – x); else right_diff = INT_MAX; if (left_diff <= right_diff) { ans.push_back(arr[left]); –left; } else { ans.push_back(arr[right]); ++right; } } } sort(ans.begin(), ans.end()); return ans; } }; [/cpp] 本代码提交AC,用时143MS。]]>

LeetCode Minimum Size Subarray Sum

209. Minimum Size Subarray Sum 209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example: 

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).  209. Minimum Size Subarray Sum


给定一个正整数数组和一个数s,要求从数组中找出最短的子串,使得子串的和大于等于s。
解法1,双指针法,O(n)。维护两个指针left和right,初始时都为0,我们的目标就是使[left,right)的和大于等于s。所以先right右移,直到和大于等于s,此时尝试缩小区间,即left也右移,在右移的过程中,更新最短子串长度,且累加和要减去left指向的数。这样不断的先移right,后移left,并更新最短长度。

代码如下,非常简洁易懂。

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums)
    {
        int n = nums.size(), left = 0, right = 0, sum = 0, ans = INT_MAX;
        while (right < n) {
            while (right < n && sum < s)
                sum += nums[right++];
            while (left <= right && sum >= s) {
                ans = min(ans, right – left);
                sum -= nums[left++];
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

本代码提交AC,用时13MS。
解法2,二分查找,O(nlgn)。我们先想想暴力方法,枚举每个left,从left开始枚举right,直到累加和第一次超过sum,更新最短长度。这样两层循环,时间复杂度是O(n^2)的。有没有办法把内层查找right的时间复杂度降低呢?
遇到子数组和的问题,马上要想到借助累加和数组。所以我们先求到原数组的累加和数组accuSum[n+1],其中accuSum[i]等于原数组中前i-1个数之和。我们利用accuSum来循环right,对于每个left,它要找一个right,使得left和right之间的和大于等于s,也就相当于在accuSum中找一个right,使得accuSum[right]>=accuSum[left]+s,等价于accuSum[right]-accuSum[left]>=s,即left到right的累加和大于等于s。因为原数组是正整数数组,所以accuSum是递增有序的,所以我们可以在accuSum中二分查找。即查找right的复杂度降为了O(lgn),所以总的复杂度就是O(nlgn)了。
完整代码如下:

class Solution {
private:
    int searchRight(vector<int>& accuSum, int l, int r, int target)
    {
        while (l <= r) {
            int m = l + (r – l) / 2;
            if (accuSum[m] == target)
                return m;
            else if (accuSum[m] > target)
                r = m – 1;
            else
                l = m + 1;
        }
        return l;
    }
public:
    int minSubArrayLen(int s, vector<int>& nums)
    {
        int n = nums.size(), ans = INT_MAX;
        vector<int> accuSum(n + 1, 0);
        for (int i = 1; i <= n; ++i)
            accuSum[i] = accuSum[i – 1] + nums[i – 1];
        for (int left = 0; left < n; ++left) {
            int right = searchRight(accuSum, left, accuSum.size() – 1, accuSum[left] + s);
            if (right == n + 1)
                break;
            ans = min(ans, right – left);
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

本代码提交AC,用时16MS。]]>

LeetCode Kth Smallest Element in a Sorted Matrix

378. Kth Smallest Element in a Sorted Matrix 378. Kth Smallest Element in a Sorted Matrix

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. 378. Kth Smallest Element in a Sorted Matrix


给定一个矩阵,该矩阵每行和每列都是有序的,要找出第k小的数。 如果只利用每行或者每列是有序的,则可以使用堆解决。我们以行为例,那么每行都是有序的,则相当于把所有行进行n路归并,然后找到第k小的数。所以我们构建一个最小堆,首先把所有行的首元素放到堆中,然后n路归并k次,每次弹出堆顶元素(即当前最小值),然后把原堆顶元素所在行的下一个元素放入堆中。k次归并结束之后,堆顶元素即为第k小的元素。 代码如下:

class Solution {
private:
    struct Node {
        int val, row, col;
        Node(int v = 0, int r = 0, int c = 0)
            : val(v)
            , row(r)
            , col(c){};
        friend bool operator<(const Node& n1, const Node& n2) { return n1.val > n2.val; }
    };
public:
    int kthSmallest(vector<vector<int> >& matrix, int k)
    {
        int n = matrix.size();
        priority_queue<Node> pn;
        for (int i = 0; i < n; ++i)
            pn.push(Node(matrix[i][0], i, 0));
        Node t;
        while (k–) {
            t = pn.top();
            pn.pop();
            if (t.col < n – 1)
                pn.push(Node(matrix[t.row][t.col + 1], t.row, t.col + 1));
        }
        return t.val;
    }
};

本代码提交AC,用时45MS。时间复杂度是O(klgn),堆的大小为n,每次归并调整堆需要lgn时间,一共需要归并k次,所以总的时间复杂度是O(klgn)。
另外用二分的方法可以同时利用行有序和列有序的特点。这种矩阵可以看成一个曲面,曲面的最低点为左上角元素left,最高点为右下角元素right,所以曲面就是从左上角向上延伸到右下角(想象一下MATLAB画的图)。那么第k小的数肯定在[left,right]范围内,我们可以二分查找这个区间。假设中点是mid,则我们在每一行找找比mid小的数有多少个,加起来如果等于cnt,则说明mid这个数排在第cnt位。因为每一行也是有序的,所以可以直接用upper_bound查找第一个比mid大的数。
代码如下:

class Solution {
public:
    int kthSmallest(vector<vector<int> >& matrix, int k)
    {
        int n = matrix.size(), left = matrix[0][0], right = matrix[n – 1][n – 1];
        while (left <= right) {
            int mid = left + (right – left) / 2;
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                cnt += upper_bound(matrix[i].begin(), matrix[i].end(), mid) – matrix[i].begin();
            }
            if (cnt < k)
                left = mid + 1;
            else
                right = mid – 1;
        }
        return left;
    }
};

本代码提交AC,用时43MS。时间复杂度是O(lgX nlgn),X为[left,right]的区间大小,ngln是对于每个mid,都需要在每一行二分查找比mid小的数的个数。
还可以将上述复杂度降为O(lgX n)。就是在找cnt,不需要每一行都二分查找,我们可以从矩阵的左下角往右上角阶梯查找,如果要查找的数更大,则往右移,否则往上移,每次查询只需要O(n)的时间,所以总时间是O(lgX n)。
代码如下:

class Solution {
private:
    int count_less_equal(vector<vector<int> >& matrix, int num)
    {
        int n = matrix.size(), i = n – 1, j = 0, cnt = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= num) {
                cnt += i + 1;
                ++j;
            }
            else
                –i;
        }
        return cnt;
    }
public:
    int kthSmallest(vector<vector<int> >& matrix, int k)
    {
        int n = matrix.size(), left = matrix[0][0], right = matrix[n – 1][n – 1];
        while (left <= right) {
            int mid = left + (right – left) / 2;
            int cnt = count_less_equal(matrix, mid);
            if (cnt < k)
                left = mid + 1;
            else
                right = mid – 1;
        }
        return left;
    }
};

本代码提交AC,用时39MS。

LeetCode Heaters

LeetCode Heaters Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses. Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters. So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters. Note:

  1. Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
  2. Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
  3. As long as a house is in the heaters’ warm radius range, it can be warmed.
  4. All the heaters follow your radius standard and the warm radius will the same.
Example 1:
Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.
Example 2:
Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

给定房子和加热器的位置,问加热器的最小半径是所少才能使所有房子都在加热的范围之内。一个加热器的加热范围是一个圆,所有加热器的加热半径都是一样的。 要保证每个房子都在加热范围之内,且加热器的半径最小,则房子i肯定被紧邻i前后的两个加热器之一覆盖,其他加热器距离i的距离肯定比紧邻i前后的两个加热器远。比如x, i, y,i表示房子坐标,x和y分别表示紧邻i的两个加热器坐标,则覆盖i的最小半径应该是min(i-x,y-i)。 所以问题就转换为对每个房子坐标i,去加热器坐标数组中找到紧邻i前后的两个加热器坐标x和y,然后根据上述公式更新结果。为了便于查找,先对加热器坐标排序,然后直接二分查找就好了。 代码如下: [cpp] class Solution { public: int findRadius(vector<int>& houses, vector<int>& heaters) { sort(heaters.begin(), heaters.end()); int ans = 0; for (int i = 0; i < houses.size(); ++i) { int &pos = houses[i]; int r = INT_MAX; auto lb = lower_bound(heaters.begin(), heaters.end(), pos); if (lb > heaters.begin())r = min(r, pos – *(lb – 1)); auto ub = lower_bound(heaters.begin(), heaters.end(), pos); if (ub < heaters.end())r = min(r, *ub – pos); ans = max(ans, r); } return ans; } }; [/cpp] 本代码提交AC,用时89MS。 还可以自己写二分查找代码,如下: [cpp] class Solution { private: int my_lower_bound(vector<int>& v, int target) { int l = 0, r = v.size() – 1; while (l <= r) { int m = l + (r – l) / 2; if (target > v[m])l = m + 1; else r = m – 1; } return l; } public: int findRadius(vector<int>& houses, vector<int>& heaters) { sort(heaters.begin(), heaters.end()); int ans = 0, n = houses.size(), m = heaters.size(); for (int i = 0; i < n; ++i) { int &pos = houses[i]; int r = INT_MAX; int lb = my_lower_bound(heaters, pos); if (lb > 0)r = min(r, pos – heaters[lb – 1]); if (lb < m)r = min(r, heaters[lb] – pos); ans = max(ans, r); } return ans; } }; [/cpp] 本代码提交AC,用时76MS。]]>