本文是【常用算法思路分析系列】的第五篇,总结二分搜索相关的高频题目和解题思路。本文分析如下几个问题:1、求数组局部最小值问题;2、元素最左出现的位置;3、循环有序数组求最小值;4、最左原位;5、完全二叉树计算结点数;6、快速N次方。
本系列前四篇导航:
【常用算法思路分析系列】排序高频题集
【常用算法思路分析系列】字符串高频题集
【常用算法思路分析系列】栈和队列高频题集(修改版)
【常用算法思路分析系列】链表相关高频题集
二分搜索的重要提醒:
一般我们选择中点进行搜索,会写成mid = (left + right) / 2;但是当数据很大的时候,下标(left + right)就可能出现溢出的情况,此时,更安全的一种写法是:mid
= left + (right - left) / 2;
1、求数组局部最小值位置
定义局部最小的概念。arr长度为1时,arr[0]是局部最小。arr的长度为N(N>1)时,如果arr[0]无序数组arr,已知arr中任意两个相邻的数都不相等,写一个函数,只需返回arr中任意一个局部最小出现的位置即可。
思路:
解题思路其实就是根据局部最小的定义来求解。首先,拿到一个数组后,考虑两端的情况,初始端arr[0]
arr[1],则从0位置往后(右)看,数组是递减的,如果arr[N-1] > arr[N-2],则从N-1处往前(左)看,数组也是递减的,说明符合条件的中中间位置,则考察中间位置mid
= (left + right) / 2; 类似二分搜索的划分。如下:
public int getLessIndex(int[] arr) {
if(arr == null || arr.length == 0){
return -1;
}
if(arr.length == 1 || arr[0] arr[mid - 1]){
right = mid - 1;
}else if(arr[mid] > arr[mid + 1]){
left = mid + 1;
}else{
return mid;
}
}
return left;
}
或者使用递归的写法,如下:
public int getLessIndex(int[] arr) {
if(arr == null || arr.length == 0){
return -1;
}
if(arr.length == 1){
return 0;
}
return getLess(arr, 0, arr.length - 1);
}
private int getLess(int[] arr, int left, int right) {
if(left == right){
return left;
}
if(arr[left] arr[mid - 1]){
return getLess(arr, left + 1, mid - 1);
}else if(arr[mid] > arr[mid + 1]){
return getLess(arr, mid + 1, right - 1);
}
return left;
}
时间复杂度为O(logN)。
上面这个例子说明,二分搜索并不一定只在数组有序的时候才可以用,只要我们在查找的时候发现,可以留下一半,淘汰另一半,就可以使用二分搜索。
2、元素最左出现的位置
对于一个有序数组arr,再给定一个整数num,请在arr中找到num这个数出现的最左边的位置。
给定一个数组arr及它的大小n,同时给定num。请返回所求位置。若该元素在数组中未出现,请返回-1。
思路:
由于数组有序,考虑用二分搜索法快速定位到数组中值为num位置处,找到后num后,因为数组有序递增,在num左边继续遍历,找到最左边的num位置,如下:
public int findPos(int[] arr, int n, int num) {
if(arr == null || arr.length == 1){
return -1;
}
int res = -1;
int left = 0;
int right = arr.length - 1;
int mid = 0;
while(left <= right){
mid = (left + right) / 2;
if(arr[mid] > num){
right = mid - 1;
}else if(arr[mid]
3、循环有序数组求最小值
对于一个有序循环数组arr,返回arr中的最小值。有序循环数组是指,有序数组左边任意长度的部分放到右边去,右边的部分拿到左边来。比如数组[1,2,3,3,4],是有序循环数组,[4,1,2,3,3]也是。
给定数组arr及它的大小n,请返回最小值。
测试样例:
[4,1,2,3,3],5
返回:1
思路:
(1)首先设置好下标,left=0,right=arr.length-1,如果arr[left]
(2)当arr[left] >= arr[right]时,即数组为循环状态,开始二分搜索,找到中间位置mid = (left + right) / 2;如果arr[left] > arr[mid],说明最小值一定在mid左半部分;
(3)如果arr[mid] > arr[right],说明最小值一定出现在mid右半部分,否则,arr[left] <=arr[mid],arr[mid] <= arr[right],又arr[left] >= arr[right],由三个条件==> arr[left] == arr[right] == arr[mid]。
此时,需要用遍历的方式在left-->right的区间寻找最小值。(或者说,因为arr[left] == arr[right] == arr[mid],说明在[left,mid]区间内,必定有最小值,再在这个区间遍历搜索)
public static int getMin(int[] arr, int n) {
if(arr == null || arr.length == 0){
return -1;
}
if(arr.length == 1){
return arr[0];
}
int left = 0;
int right = arr.length - 1;
int mid = 0;
//下面是arr[left] >= arr[right]的情形,即数组为循环状态
while(left arr[mid]){//最小值一定在mid左半部分
right = mid;
continue;
}else if(arr[mid] > arr[right]){//最小值一定出现在mid右半部分
left = mid;
continue;
}else{
//这种情况下,arr[left] <=arr[mid],arr[mid] <= arr[right],又arr[left] >= arr[right],由三个条件==> arr[left] == arr[right] == arr[mid]
//此时,需要用遍历的方式在left-->right的区间寻找最小值
// int min = arr[left];
// for(int i = left; i <= right; i++){
// if(arr[i]
4、最左原位
有一个有序数组arr,其中不含有重复元素,请找到满足arr[i]==i条件的最左的位置。如果所有位置上的数都不满足条件,返回-1。
给定有序数组arr及它的大小n,请返回所求值。
测试样例:
[-1,0,2,3],4
返回:2
思路:
(1)先考察数组的两端,开始端如果arr[left] > n-1;或者,末端arr[right] <0;则直接返回-1;
(2)再通过二分搜索思想,mid = (left + right) / 2;比较arr[mid]和mid的值:
当arr[mid]>mid时,arr[i] = i的值只可能在mid左边;
当arr[mid]
当arr[mid]==mid时,继续寻找最左边arr[i] = i的值;
代码如下:
public int findPos(int[] arr, int n, int num) {
if(arr == null || n == 0){
return -1;
}
int left = 0;
int right = arr.length - 1;
if(arr[left] > n - 1 || arr[right] <0){
return -1;
}
int mid = 0;
int res = -1;
while(left <= right){
if (arr[left] > left || arr[right] mid){
right = mid - 1;
}else if(arr[mid]
5、完全二叉树计数
给定一棵完全二叉树的根节点root,返回这棵树的节点个数。如果完全二叉树的节点数为N,请实现时间复杂度低于O(N)的解法。
给定树的根结点root,请返回树的大小。
思路:
(1)首先一直遍历到根节点的左子树的最左边,得到树的高度high;
(2)再遍历根节点的右子树的最左边,得到右子树的高度rightHigh;
(3)如果high==rightHigh,表示根节点的左子树为满二叉树,高度为high,此时左子树可以直接根据满二叉树的性质求出节点数量,再对右子树递归遍历;
(4)如果high!=rightHigh,表示根节点的右子树为满二叉树,高度为high - 1,此时右子树可以直接根据满二叉树的性质求出节点数量,再对左子树递归遍历;
代码如下:
public int count(TreeNode root) {
if(root == null){
return 0;
}
int high = 0;
TreeNode node = root;
while(node != null){
high++;
node = node.left;
}
int rightHigh = 0;
node = root;
while(node != null){
rightHigh++;
node = node.left;
}
if(high == rightHigh){//表示根节点的左子树为满二叉树,高度为high - 1
return (int) (Math.pow(2, high - 1)) + count(root.right);
}else{
return (int) (Math.pow(2, rightHigh - 1)) + count(root.left);
}
}
6、快速N次方
如何更快的求一个整数k的n次方。如果两个整数相乘并得到结果的时间复杂度为O(1),得到整数k的N次方的过程请实现时间复杂度为O(logN)的方法。
给定k和n,请返回k的n次方,为了防止溢出,请返回结果Mod 1000000007的值。
测试样例:
2,3
返回:8
思路:
以10^13为例,首先我们将13以二进制表示如下:0000 1101
10^13 = 10^1 * 10^4 * 10^8
我们根据二进制的长度,依次获取
10^1
10^2 = 10^1 * 10^1;
10^4 = 10^2 * 10^2;
10^8 = 10^4 * 10^4;
...
在这个过程中,如果二进制位上为1,则累乘起来,代码如下:
public int getPower(int k, int N) {
if(k == 0){
return 0;
}
if(k == 1 || N == 0){
return 1;
}
long modNum = 1000000007;
long res = 1;
long temp = k;
for(; N > 0; N >>= 1){
if((N & 1) != 0){
res *= temp;
}
temp = (temp * temp) % modNum;
res = res % modNum;
}
return (int) res;
}
下一篇将是与二叉树相关。
【常用算法思路分析系列】与二分搜索相关高频题