? 时间复杂度小练习
? 递归与非递归的权衡
? 二分的三大痛点
? 通用的二分法模板
? 二分位置 之 圈圈叉叉 Binary Search on Index – OOXX
? 找到满足某个条件的第一个位置或者最后一个位置
?二分位置 之 保留一半 Binary Search on Index – Half half
? 保留有解的一半，或者去掉无解的一半
T(n) = T(n/2) + O(1)
=T(n/4) + O(1) + O(1)
=T(n/8) + O(1) +O(1) +O(1)
=T(1) + logn * O(1)
T(n) = T(n/2) + O(n)
=T(n/4) + O(n) + O(n/2)
=T(n/8) + O(n) +O(n/2) +O(n/4)
=T(1) + )(n * (1 + 1/2 + 1/4 + … + 1/n)
≈O(2n)
≈O(n)
? O(1) 极少
? O(logn) 几乎都是二分法
? O(√n) 几乎是分解质因数
? O(n) 高频
? O(nlogn) 一般都可能要排序
? O(n2) 数组，枚举，动态规划
? O(n3) 数组，枚举，动态规划
? O(2^n) 与组合有关的搜索 combination
? O(n!) 与排列有关的搜索 permutation
比O(n)更优的时间复杂度，几乎只能是O(logn)的二分法
经验之谈：根据时间复杂度倒推算法是面试中的常用策略
记住：不要自己下判断，要跟面试官讨论！
1.start + 1 < end
2.start + (end – start) / 2
3.A[mid] ==,
4.A[start] A[end] ? target
因为如果要求小于的话，那么退出的条件就是只有等于
假设问题为在[2,2]中找2最后一次出现的位置，就会
|
1
2
3
4
5
6
7
8
9
|
while (start < end) {mid = (0 + 1) / 2 = 0;if (mid == target) {start = mid;} |
永远都不能等于，所以死循环了。
应该用相邻或者相等退出，即 start + 1 < end
二分不是确定答案在哪, 而是减少搜索范围
分三种情况:
num[mid] == target
num[mid] target
根据题意 找last position 先比较 num[end] == target
数组和指针要看NULL和length = 0 的情况
一般会给你一个数组, 让你找数组中第一个/最后一个满足某个条件的位置
即在一个如下数列: OOOOOOO…OOXX….XXXXXX中找第一个X, 做后一个O类似
First version that is bad version
Given a big sorted array with positive integers sorted by ascending order. The array is so big so that you can not get the length of the whole array directly, and you can only access the kth number by ArrayReader.get(k) (or ArrayReader->get(k) for C++). Find the first index of a target number. Your algorithm should be in O(log k), where k is the first index of the target number.
Return -1, if the number doesn’t exist in the array.
Notice
If you accessed an inaccessible index (outside of the array), ArrayReader.get will return 2,147,483,647.
先以跨度加倍的方式(即index位置为1, 2, 4, 8…..2^x, 2^(x+1)), 找到第一个比target大的数
再二分查找target
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
Notice
You may assume no duplicate exists in the array.
画图表示的话呢
就是在两段上升区间, 找到第一个x.
target可以定为: 第一个比first number小的数, 或者第一个比last number小的数.
因为一段上升空间和一个空区间是两段上升区间的一个corner case, 如图:
所以只能选第一个比end小的数
主要看特殊情况,决定选first number还是last number,上升找最小值比尾巴
An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.
01矩阵中，所有的1连成一片，找到最小的能覆盖所有1的矩形, 输入给出了其中一个1的位置
1.Search a 2D Matrix
http://www.lintcode.com/en/problem/search-a-2d-matrix/
二分一次行,二分一次列, 两次二分
2.Search for a Range
http://www.lintcode.com/en/problem/search-for-a-range/
即找出黑色虚线虚线框
黑色虚线框是什么呢, 是上下左右四个位置:
左:第一个出现绿色的列
右:最后一个出现绿色的列
上:第一个绿的行
下:最后一个绿的行
所以找左右需要的时间复杂度为: colSize *log(rowSize)
上下的时间复杂度为:rowSize *log(colSize)
最终的时间复杂度为: nlog(m) + mlog(n)
Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top.
在先增后减的序列中找最大值
找第一个下降的点
There is an integer array which has the following features:
We define a position P is a peek if:
A[P] > A[P-1] && A[P] > A[P+1]
找到任意一个peak, 前面数个上升, 后面无数个下降
for一下,找比左边和右边都大的数, O(n)
对于一个不是中间的数,有如下四种情况:
第一种直接返回, 其他情况,保留先增后减的一半.
图解:
M1可能落在左半边, 也可能落在右半边. M1 >= S1, 左; M1 < S1, 右
即把数组分为了两部分,粉色部分[S,M]和橙色部分[M]
我们想去掉一半, 让它仍保持RSA(rotated sorted array)
如果M落在左, 切掉[S,M]; 如果M落在右, 切掉[M,E]
Given a rotated sorted array, recover it to sorted array in-place.
Example [4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]
思路：45 翻转变54， 123翻转变321，现有54321，再全翻转一遍
public class Solution {
/**
* @param nums: The rotated sorted array
* @return: The recovered sorted array
*/
private void reverse(ArrayList<Integer> nums, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
int temp = nums.get(i);
nums.set(i, nums.get(j));
nums.set(j, temp);
}
}
public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
for (int index = 0; index < nums.size() - 1; index++) {
if (nums.get(index) > nums.get(index + 1)) {
reverse(nums, 0, index);
reverse(nums, index + 1, nums.size() - 1);
reverse(nums, 0, nums.size() - 1);
return;
}
}
}
}
这道题，因为最坏的情况下, n-1个数的位置都要移动, 所以时间复杂度不会小于O(n).
难点在于空间复杂度上, 只用O(1).
在数组操作中, 对于两个元素之间的操作, O(1)的有一个swap.
运用swap和双指针, 对于一个数组, 就有一个O(n)的操作叫做reverse.
所以就用reverse啦
类似的还有rotate string这道题
Write an efficient algorithm that searches for a value in an m x n matrix, return the occurrence of it.
This matrix has the following properties:
橙色线上，从左往右，后一个一定大于前一个；
蓝色线上，后一个可能和前一个相等；
所以左下到右上这条线上呢，相当于中间的位置mid，跟它比较找结果。
public class Solution {
/**
* @param matrix: A list of lists of integers
* @param: A number you want to search in the matrix
* @return: An integer indicate the occurrence of target in the given matrix
*/
public int searchMatrix(int[][] matrix, int target) {
// check corner case
if (matrix == null || matrix.length == 0) {
return 0;
}
if (matrix[0] == null || matrix[0].length == 0) {
return 0;
}
// from bottom left to top right
int n = matrix.length;
int m = matrix[0].length;
int x = n - 1;
int y = 0;
int count = 0;
while (x >= 0 && y < m) {
if (matrix[x][y] < target) {
y++;
} else if (matrix[x][y] > target) {
x--;
} else {
count++;
x--;
y++;
}
}
return count;
}
}
原文：https://www.cnblogs.com/jiuzhangsuanfa/p/9895642.html