[关闭]
@Sarah 2016-01-01T02:07:11.000000Z 字数 15217 阅读 1852

2 Binary Search/Sorted Array

算法

电面比onsite简单一些 ，有斐波那契数列之类的，二分搜索

简历： 能否得到面试重要因素，HR关注关键词 学校 之前实习 是不是FLAG（大公司）的实习生，

专门 ：关键词查找，有一些印度人帮你改简历，插入各种各样的关键词，方便于被检索到
面试官角度：一 education，因为你已经进入面试了，不会因为学校不好筛掉。（大致猜你的水平，以知道给你出什么难度的题）
二 实习 基本认识 衡量你水平。
不推荐自己写跟算法竞赛相关，不推荐写！对于你过面试没有任何好处，看到你这个背景以后会把题目难度加大！！！

你的project没有项目肯定会被刷掉！！非常重要！！你必须有一个project，什么项目都没做过只上过课，完蛋。
写的时候写对于项目做过什么事情，产生什么影响力，你做的事情对项目产生什么影响，不是只写你做了什么。

给人感觉是不踏实，冠冕堂皇。不能恨信服这个项目就是你做的，觉得你吹牛
他只写了项目是什么：要写你做了什么以后对项目产生什么影响力
因为你的参与，系统性能提高多少，服务多少用户，准确率提高多少，写具体一点，攻克什么难关，这个事儿你干和别人干什么区别。

应届毕业生：简历写一页 PHD写两页 不要多写 挑重要的写 千万别长篇大论，不专业

二分查找：给你一个sorted数组，再给一个整数，找这个整数的位置，找不着return负一

排序了才能用二分查找，电话本那个！！！！！
此处输入图片的描述
1先找到中间的位置 第4个 13比5大，所以右边不要了，
把end挪到mid的位置
mid找到5了

时间复杂度：每次减少一半,n个数：tn/2+O(1) 是比较的复杂度，
整个复杂度是O (LOG n)

递归：代码简洁 两三行 写出来出错概率少
坏处：耗费栈空间,层数多了容易栈溢出,栈空间启示很小,不大 每个程序都要一个栈.
while：不用占用栈空间 容易写错 代码多几行 难理解

面试用不用递归：
只要用非递归不是写不出来，你就用非递归写.
如果用递归简单很多，用递归.

二分法建议用非递归来写：递归不会挂，但是不太好，因为不差那么多，希望你能平时 在工程的时候避免递归，因为耗费栈空间，防止栈溢出（递归死循环）

Binary search

is a famous question in algorithm. For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity. If the target number does not exist in the array, return -1. Example If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.
返回第一次出现的位置

  1. class Solution {
  2.     /**
  3.      * @param nums: The integer array.
  4.      * @param target: Target to find.
  5.      * @return: The first position of target. Position starts from 0.
  6.      */
  7.     public int binarySearch(int[] nums, int target) {
  8.         if (nums == null || nums.length == 0) {
  9.             return -1;
  10.         }
  12.         int start = 0, end = nums.length - 1;
  13.         while (start + 1 < end) {
  14.         //这个结束怎么写很重要
  15.         //当数组里只有两个数的时候(>=)就可以退出循环了
  16.         **//在任何二分法题目中都可以使用这个**但是别忘了结束的时候要多一层判断，是start是我们要的target还是end是我们要的target
  17.             int mid = start + (end - start) / 2;
  18.             if (nums[mid] == target) {
  19.                 end = mid;  
  20.             } else if (nums[mid] < target) {
  21.                 start = mid;
  22.             } else {
  23.                 end = mid;
  24.             }
  25.         }
  26.         if (nums[start] == target) {
  27.             return start;
  28.         }
  29.         if (nums[end] == target) {
  30.             return end;
  31.         }
  32.             //因为题目让我们找first所以先比较start,如果让我们找last position ，那就先比较end 
  33.         return -1;
  34.     }
  35. }

while结束循环怎么写？
当我的循环循环到数组里只有最多两个数的时候就可以退出了，在任何二分法都用start+ 一 后面不加以也不减一 但是后面要加一个特殊判断

四个要点

记住通用的解法 有时候有点麻烦 但是通用！！不用每个题都重新做 思考的难度减小很多 ！！！

1 start+1

2 start + (end - start) / 2==(start+end)/2 前者这么写不会溢出 向面试官展示你很细心

3 = < > 的时候到底是谁挪过去 3种情况

4循环结束之后看看到底哪个是我们要的target 否则返回-1

你会觉得啰嗦，但其实通用写法 每个题都可以这么写！模板！

如果变成了last position:1先考虑end再考虑start,2当他们等的时候，把start挪到middle
一
二分法四个要素

二 什么是转圈排序数组
找最小 找目标

三 找中位数排序数组

four 三部翻转法

Search for a Range

Given a sorted array of n integers, find the starting and ending position of a given target value.
If the target is not found in the array, return [-1, -1].
Have you met this question in a real interview? Yes
Example
Given [5, 7, 7, 8, 8, 10] and target value 8,把8的区间找到
return [3, 4].
Challenge
O(log n) time.

1找第一次出现的位置，再找最后一次出现的位置
写两个二分法，第一个二分法找到第一个位置，第二个二分法找第二个位置

  1. public class Solution {
  2.     public int[] searchRange(int[] A, int target) {
  3.         if (A.length == 0) {
  4.             return new int[]{-1, -1};
  5.         }
  7.         int start, end, mid;
  8.         int[] bound = new int[2]; 
  10.         // search for left bound把end挪过去,先看start
  11.         start = 0; 
  12.         end = A.length - 1;
  13.         while (start + 1 < end) {
  14.             mid = start + (end - start) / 2;
  15.             if (A[mid] == target) {
  16.                 end = mid;
  17.             } else if (A[mid] < target) {
  18.                 start = mid;
  19.             } else {
  20.                 end = mid;
  21.             }
  22.         }
  23.         if (A[start] == target) {
  24.             bound[0] = start;
  25.         } else if (A[end] == target) {
  26.             bound[0] = end;
  27.         } else {
  28.             bound[0] = bound[1] = -1;
  29.             return bound;
  30.         }
  32.         // search for right bound，把start挪过去,先看end
  33.         start = 0;
  34.         end = A.length - 1;
  35.         while (start + 1 < end) {
  36.             mid = start + (end - start) / 2;
  37.             if (A[mid] == target) {
  38.                 start = mid;
  39.             } else if (A[mid] < target) {
  40.                 start = mid;
  41.             } else {
  42.                 end = mid;
  43.             }
  44.         }
  45.         if (A[end] == target) {
  46.             bound[1] = end;
  47.         } else if (A[start] == target) {
  48.             bound[1] = start;
  49.         } else {
  50.             bound[0] = bound[1] = -1;
  51.             return bound;
  52.         }
  54.         return bound;
  55.     }
  56. }

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples. [1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

  1. // version 1: find the first position >= target
  2. public class Solution {
  3.     public int searchInsert(int[] A, int target) {
  4.         if (A == null || A.length == 0) {
  5.             return 0;
  6.         }
  7.         int start = 0, end = A.length - 1;
  9.         while (start + 1 < end) {
  10.             int mid = start + (end - start) / 2;
  11.             if (A[mid] == target) {
  12.                 return mid;//找到了直接返回
  13.             } else if (A[mid] < target) {
  14.                 start = mid;//小于就start挪过去
  15.             } else {
  16.                 end = mid;//大于就end挪过去
  17.             }
  18.         }
  19.         //考虑两个数特殊情况（模板直接套过来）
  20.         //first posotion所以看start
  21.         if (A[start] >= target) {
  22.             return start;
  23.         } else if (A[end] >= target) {
  24.             return end;
  25.         } else {
  26.             return end + 1;//也可以返回长度
  27.         }
  28.     }
  29. }
  31. // version 2: find the last position < target, return +1， 要特判一下target小于所有数组里面的元素
  33. public class Solution {
  34.     public int searchInsert(int[] A, int target) {
  35.         if (A == null || A.length == 0) {
  36.             return 0;
  37.         }
  38.         int start = 0;
  39.         int end = A.length - 1;
  40.         int mid;
  42.         if (target < A[0]) {
  43.             return 0;
  44.         }
  45.         // find the last number less than target
  46.         while (start + 1 < end) {
  47.             mid = start + (end - start) / 2;
  48.             if (A[mid] == target) {
  49.                 return mid;
  50.             } else if (A[mid] < target) {
  51.                 start = mid;
  52.             } else {
  53.                 end = mid;
  54.             }
  55.         }
  57.         if (A[end] == target) {
  58.             return end;
  59.         }
  60.         if (A[end] < target) {
  61.             return end + 1;
  62.         }
  63.         if (A[start] == target) {
  64.             return start;
  65.         }
  66.         return start + 1;
  67.     }
  68. }

之前是有一个实在的数
这个则是这个数不一定在，要找到那个位置，如何用逻辑表述这个位置
描述：找到第一个>=target的数
先想清楚这个事再动笔写
first position/ last position 临界点
找不着：return 长度（最后一个）

Write an efficient algorithm that searches for a value in an m x n matrix.

This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. For example, Consider the following matrix: [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] Given target = 3, return true
第一行严格小于第二行，第二行严格小于第三行，给一个3问有没有

法1：两次二分，先二分确认3应该在哪一行，再二分找出3在哪一列
O(log n+log m)

法2：只用一次二分。把数组看成一维数组连起来，元素个数 start=o,end-n-1，
要用公式求mid对应哪个数：
matrix[start / column][start % column]
求对应到哪个位置，再跟target去比
O(log n+log m)

  1. // Binary Search Twice
  2. public class Solution {
  3.     public boolean searchMatrix(int[][] matrix, int target) {
  4.         if (matrix == null || matrix.length == 0) {
  5.             return false;
  6.         }
  7.         if (matrix[0] == null || matrix[0].length == 0) {
  8.             return false;
  9.         }
  11.         int row = matrix.length;
  12.         int column = matrix[0].length;
  14.         // find the row index, the last number <= target 
  15.         int start = 0, end = row - 1;
  16.         while (start + 1 < end) {
  17.             int mid = start + (end - start) / 2;
  18.             if (matrix[mid][0] == target) {
  19.                 return true;
  20.             } else if (matrix[mid][0] < target) {
  21.                 start = mid;
  22.             } else {
  23.                 end = mid;
  24.             }
  25.         }
  26.         if (matrix[end][0] <= target) {
  27.             row = end;
  28.         } else if (matrix[start][0] <= target) {
  29.             row = start;
  30.         } else {
  31.             return false;
  32.         }
  34.         // find the column index, the number equal to target
  35.         start = 0;
  36.         end = column - 1;
  37.         while (start + 1 < end) {
  38.             int mid = start + (end - start) / 2;
  39.             if (matrix[row][mid] == target) {
  40.                 return true;
  41.             } else if (matrix[row][mid] < target) {
  42.                 start = mid;
  43.             } else {
  44.                 end = mid;
  45.             }
  46.         }
  47.         if (matrix[row][start] == target) {
  48.             return true;
  49.         } else if (matrix[row][end] == target) {
  50.             return true;
  51.         }
  52.         return false;
  53.     }
  54. }
  56. // Binary Search Once
  57. public class Solution {
  58.     public boolean searchMatrix(int[][] matrix, int target) {
  59.         if (matrix == null || matrix.length == 0) {
  60.             return false;
  61.         }
  62.         if (matrix[0] == null || matrix[0].length == 0) {
  63.             return false;
  64.         }
  66.         int row = matrix.length, column = matrix[0].length;
  67.         int start = 0, end = row * column - 1;
  69.         while (start + 1 < end) {
  70.             int mid = start + (end - start) / 2;
  71.             int number = matrix[mid / column][mid % column];
  72.             if (number == target) {
  73.                 return true;
  74.             } else if (number < target) {
  75.                 start = mid;
  76.             } else {
  77.                 end = mid;
  78.             }
  79.         }
  81.         if (matrix[start / column][start % column] == target) {
  82.             return true;
  83.         } else if (matrix[end / column][end % column] == target) {
  84.             return true;
  85.         }
  87.         return false;
  88.     }
  89. }

如果你的矩阵里有重复怎么办？每行是递增的 每一列是递增的 但有重复

Search a 2D Matrix II

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:

Integers in each row are sorted from left to right.
Integers in each column are sorted from up to bottom.
No duplicate integers in each row or column.
Have you met this question in a real interview? Yes
Example
Consider the following matrix:
[
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]
]
Given target = 3, return 2.
O(m+n) time and O(1) extra space
找3出现了几次

法1：四分法，先二分一个对角线上的中位数，然后二分成更小的矩阵
n*m个数，tn=tn/4+o(log n)
法2：从左下角或者右上角开始找这个数，每一列是递增的，这一列就删了，往上走126是这一列最小的，所以把这一行删掉
这个数比120小我就往右走，比120大我就往上走
等于120，就把这个数记下来，再往右上走，每次可以去掉一列/一行
走出去矩阵O（n+m）

  1. public class Solution {
  2.     /**
  3.      * @param matrix: A list of lists of integers
  4.      * @param: A number you want to search in the matrix
  5.      * @return: An integer indicate the occurrence of target in the given matrix
  6.      */
  7.     public int searchMatrix(int[][] matrix, int target) {
  8.         // check corner case
  9.         if (matrix == null || matrix.length == 0) {
  10.             return 0;
  11.         }
  12.         if (matrix[0] == null || matrix[0].length == 0) {
  13.             return 0;
  14.         }
  16.         // from bottom left to top right
  17.         int n = matrix.length;
  18.         int m = matrix[0].length;
  19.         int x = n - 1;
  20.         int y = 0;
  21.         int count = 0;
  23.         while (x >= 0 && y < m) {
  24.             if (matrix[x][y] < target) {
  25.                 y++;
  26.             } else if (matrix[x][y] > target) {
  27.                 x--;
  28.             } else {
  29.                 count++;
  30.                 x--;
  31.                 y++;
  32.             }
  33.         }
  34.         return count;
  35.     }
  36. }

此处输入图片的描述
此处输入图片的描述

核心

每次关注first 和last的点

First Bad Version

The code base version is an integer start from 1 to n. One day, someone committed a bad version in the code case, so it caused this version and the following versions are all failed in the unit tests. Find the first bad version.
You can call isBadVersion to help you determine which version is the first bad one. The details interface can be found in the code's annotation part.
Have you met this question in a real interview? Yes
Example
Given n = 5:
isBadVersion(3) -> false
isBadVersion(5) -> true
isBadVersion(4) -> true
Here we are 100% sure that the 4th version is the first bad version.
Note
Please read the annotation in code area to get the correct way to call isBadVersion in different language. For example, Java is SVNRepo.isBadVersion(v)
手动测试哪个版本挂了，但是调用isBadVersion很耗费的，所以用二分法
看到fierst就想二分
1 先看n/2 ,若是好的，
2 再看n/2-n

直接套模板

  1. /**
  2.  * public class GitRepo {
  3.  *     public static boolean isBadVersion(int k);
  4.  * }
  5.  * you can use GitRepo.isBadVersion(k) to judge whether 
  6.  * the kth code version is bad or not.
  7. */
  8. class Solution {
  9.     /**
  10.      * @param n: An integers.
  11.      * @return: An integer which is the first bad version.
  12.      */
  13.     public int findFirstBadVersion(int n) {
  14.         int start = 1, end = n;
  15.         while (start + 1 < end) {
  16.             int mid = start + (end - start) / 2;
  17.             if (SVNRepo.isBadVersion(mid)) {
  18.                 end = mid;
  19.             } else {
  20.                 start = mid;
  21.             }
  22.         }
  24.         if (SVNRepo.isBadVersion(start)) {
  25.             return start;
  26.         }
  27.         return end;
  28.     }
  29. }

Find Peak Element

There is an integer array which has the following features:
The numbers in adjacent positions are different.
A[0] < A1 && A[A.length - 2] > A[A.length - 1].
We define a position P is a peek if:
A[P] > A[P-1] && A[P] > A[P+1]
Find a peak element in this array. Return the index of the peak.
Have you met this question in a real interview? Yes
Example
Given [1, 2, 1, 3, 4, 5, 7, 6]
Return index 1 (which is number 2) or 6 (which is number 7)
找峰值：一个数组先上升 后下降，然后找中间一个点P ,大于前一个数也大于后一个数，并且相邻的数不一样
如果有很多peak随便找一个就行

最差的结果：for循环一遍 o(n)
o(1)不现实， o(根号n)没有题， o(log n)就用这个方法
log n的算法：二分法 、[倍增法（很少）：第2 4 6 8 个找target]
1峰值在左
2 峰值在右
3左右都有峰值

  1. class Solution {
  2.     /**
  3.      * @param A: An integers array.
  4.      * @return: return any of peek positions.
  5.      */
  6.     public int findPeak(int[] A) {
  7.         // write your code here
  8.         int start = 1, end = A.length-2; // 1.答案在之间，2.不会出界 
  9.         while(start + 1 <  end) {
  10.             int mid = (start + end) / 2;
  11.             if(A[mid] < A[mid - 1]) {
  12.                 end = mid;
  13.             } else if(A[mid] < A[mid + 1]) {
  14.                 start = mid;
  15.             } else {
  16.                 end = mid;
  17.             }
  18.         }
  19.         if(A[start] < A[end]) {
  20.             return end;
  21.         } else { 
  22.             return start;
  23.         }
  24.     }
  25. }

寻找旋转排序数组中的最小值

假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。
你需要找到其中最小的元素。
你可以假设数组中不存在重复的元素。
您在真实的面试中是否遇到过这个题？ Yes
样例
给出[4,5,6,7,0,1,2] 返回 0
第一个数/最后一个数
把4挑出来，和二分哪个数比，是7>4所以小的在右边
把2挑出来，和二分哪个数比，是7>4所以小的在右边
要么扔掉右边，要么扔左边
图：一段上升，然后掉下来另一段上升
不能用start去比

  1. public class Solution {
  2.     /**
  3.      * @param num: a rotated sorted array
  4.      * @return: the minimum number in the array
  5.      */
  6.     public int findMin(int[] nums) {
  7.         if (nums == null || nums.length == 0) {
  8.             return -1;
  9.         }
  11.         int start = 0, end = nums.length - 1;
  12.         int target = nums[nums.length - 1];
  14.         // find the first element <= target
  15.         while (start + 1 < end) {
  16.             int mid = start + (end - start) / 2;
  17.             if (nums[mid] <= target) {
  18.                 end = mid;
  19.             } else {
  20.                 start = mid;
  21.             }
  22.         }
  23.         if (nums[start] <= target) {
  24.             return nums[start];
  25.         } else {
  26.             return nums[end];
  27.         }
  28.     }
  29. }

1考虑极端情况（没有旋转）
2图像这么画
3问重复元素怎么办？就不能用二分了，黑盒测试：只能用o（n）方法，因为的挨个测试

Search in Rotated Sorted Array

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).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Have you met this question in a real interview? Yes
Example
For [4, 5, 1, 2, 3] and target=1, return 2.
For [4, 5, 1, 2, 3] and target=0, return -1.

非常重要

1会二分法模板
2旋转array会画图 想象成这种数组

for循环可以解决
二分：
1而分到第一个上升区间
2二分到第二个上升区间

1首先学会画图 面试的时候也要画图！重要技巧
此处输入图片的描述

分成四种情况
先考虑图中的左上升情况
求二分法中点m
一： m>s：m在第一段：

1：t在sm中间--E挪到M，在SE两点中间继续二分法（右半边扔）
2T不再sm中间，t>m/ t

二：m 

  1. public class Solution {
  2.     public int search(int[] A, int target) {
  3.         if (A == null || A.length == 0) {
  4.             return -1;
  5.         }
  7.         int start = 0;
  8.         int end = A.length - 1;
  9.         int mid;
  11.         while (start + 1 < end) {
  12.             mid = start + (end - start) / 2;
  13.             if (A[mid] == target) {
  14.                 return mid;
  15.             }
  16.             if (A[start] < A[mid]) {
  17.                 // situation 1, red line
  18.                 if (A[start] <= target && target <= A[mid]) {
  19.                     end = mid;
  20.                 } else {
  21.                     start = mid;
  22.                 }
  23.             } else {
  24.                 // situation 2, green line
  25.                 if (A[mid] <= target && target <= A[end]) {
  26.                     start = mid;
  27.                 } else {
  28.                     end = mid;
  29.                 }
  30.             }
  31.         } // while
  33.         if (A[start] == target) {
  34.             return start;
  35.         }
  36.         if (A[end] == target) {
  37.             return end;
  38.         }
  39.         return -1;
  40.     }
  41. }

sorted array

Merge Sorted Array 基本功题 一定要回 不会就挂了

Given two sorted integer arrays A and B, merge B into A as one sorted array.
Have you met this question in a real interview? Yes
Example
A = [1, 2, 3, empty, empty], B = [4, 5]
After merge, A will be filled as [1, 2, 3, 4, 5]
Note
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.
A和B merge 到A，A有足够大的空间

法1：像下面那个题一样从头开始比，但是缺点是如果前面有一个要放进A前面的话，A整个后面都要挪动，时间复杂度太高 O（n平方）

法2：比较A和B的尾，从最后开始放。因为空位在后面，应该从最大的开始比

  2. class Solution {
  3.     /**
  4.      * @param A: sorted integer array A which has m elements, 
  5.      *           but size of A is m+n
  6.      * @param B: sorted integer array B which has n elements
  7.      * @return: void
  8.      */
  9.     public void mergeSortedArray(int[] A, int m, int[] B, int n) {
  10.         int i = m-1, j = n-1, index = m + n - 1;
  11.         while (i >= 0 && j >= 0) {
  12.             if (A[i] > B[j]) {
  13.                 A[index--] = A[i--];
  14.             } else {
  15.                 A[index--] = B[j--];
  16.             }
  17.         }
  18.         while (i >= 0) {
  19.             A[index--] = A[i--];
  20.         }
  21.         while (j >= 0) {
  22.             A[index--] = B[j--];
  23.         }
  24.     }
  25. }

Merge Sorted Array II

Merge two given sorted integer array A and B into a new sorted integer array.
Have you met this question in a real interview? Yes
Example
A=[1,2,3,4]
B=[2,4,5,6]
return [1,2,2,3,4,4,5,6]
A和Bmerge到新的数组

假设
A 2 4 6 8
B 3 5 7 9
比较a0 和b0,谁小就把谁拿到新数组c里
a0 b0再和a1比，谁小把谁拿过来
（画成一个一个小格子）

  1. class Solution {
  2.     /**
  3.      * @param A and B: sorted integer array A and B.
  4.      * @return: A new sorted integer array
  5.      */
  6.     public ArrayList<Integer> mergeSortedArray(ArrayList<Integer> A, ArrayList<Integer> B) {
  7.         int len = B.size();
  8.         for (int i = 0; i < len; ++i) 
  9.             A.add(B.get(i));
  10.         Collections.sort(A);
  11.         return A;
  12.     }
  13. }

难题注意：⬇️

重要 Median of two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.
Have you met this question in a real interview? Yes
Example
Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.
Given A=[1,2,3] and B=[4,5], the median is 3.
Challenge
The overall run time complexity should be O(log (m+n)).
给两个有序数组求中位数

1出现了3.5 有的中位数是不存在于数组里的
难 做不出来很正常

姐妹题：find the Kth sorted arrary ，在两个数组里找第K大。直接比就可以了，
k=(A+B)/2
"我不画图我也讲不清楚！"
找第一大：比较AB头两个数，复杂度跟K有关系，和AB没关系。
暴力解法：把两个数组merge到第K个。o(k) 慢1
最优o(log k)二分，把K转化成找k/2这个位置。
比较A的第K/2 和B的k/2这两个数
若A第(k/2)<=B第(k/2)：A的前k/2个数都小于AB合并以后第K个数的前面
然后把A前k/2个数都扔掉
剩下的数组里，要求的第K大的数变成了第k-k/2个
o(log k)

如何扔掉A的前k/2个数组？记下每个数字的起始位置（偏移量）

找median转化成找第k大

  1. public class Solution {
  2.     public double findMedianSortedArrays(int A[], int B[]) {
  3.         int len = A.length + B.length;
  4.         if (len % 2 == 1) {
  5.             return findKth(A, 0, B, 0, len / 2 + 1);
  6.         }
  7.         //如果初2余1那就是找那个数
  8.         return (
  9.             findKth(A, 0, B, 0, len / 2) + findKth(A, 0, B, 0, len / 2 + 1)
  10.         ) / 2.0;
  11.     }
  12. 1：40``
  13.     // find kth number of two sorted array
  14.     public static int findKth(int[] A, int A_start,
  15.                               int[] B, int B_start,
  16.                               int k){       
  17.         if (A_start >= A.length) {
  18.             return B[B_start + k - 1];
  19.         }
  20.         if (B_start >= B.length) {
  21.             return A[A_start + k - 1];
  22.         }
  24.         if (k == 1) {
  25.             return Math.min(A[A_start], B[B_start]);
  26.         }
  28.         int A_key = A_start + k / 2 - 1 < A.length
  29.                     ? A[A_start + k / 2 - 1]
  30.                     : Integer.MAX_VALUE;
  31.         int B_key = B_start + k / 2 - 1 < B.length
  32.                     ? B[B_start + k / 2 - 1]
  33.                     : Integer.MAX_VALUE; 
  35.         if (A_key < B_key) {
  36.             return findKth(A, A_start + k / 2, B, B_start, k - k / 2);
  37.         } else {
  38.             return findKth(A, A_start, B, B_start + k / 2, k - k / 2);
  39.         }
  40.     }
  41. }

题目不要求不用去重，不要自己假设
o(1)额外空间
时间o(log k)

Recover Rotated Sorted Array

Given a rotated sorted array, recover it to sorted array in-place.
Have you met this question in a real interview? Yes
Example
[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]
Challenge
In-place, O(1) extra space and O(n) time.
Clarification
What is rotated array?
For example, the orginal array is [1,2,3,4], The rotated array of it can be [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]
给你一个rotated sorted array 你把它变回来
难点：o（1）额外空间 在原地做
时间o(n)不能再短了

三步翻转法
45123：
1：54
2：321
3：12345
三次reverse,指针指向头尾，然后换位置翻转

  2. import java.util.ArrayList;
  5. public class Solution {
  6.     /**
  7.      * @param nums: The rotated sorted array
  8.      * @return: The recovered sorted array
  9.      */
  10.     private void reverse(ArrayList<Integer> nums, int start, int end) {
  11.         for (int i = start, j = end; i < j; i++, j--) {
  12.             int temp = nums.get(i);
  13.             nums.set(i, nums.get(j));
  14.             nums.set(j, temp);
  15.         }
  16.     }
  18.     public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
  19.         for (int index = 0; index < nums.size() - 1; index++) {
  20.             if (nums.get(index) > nums.get(index + 1)) {
  21.                 reverse(nums, 0, index);
  22.                 reverse(nums, index + 1, nums.size() - 1);
  23.                 reverse(nums, 0, nums.size() - 1);
  24.                 return;
  25.             }
  26.         }
  27.     }
  28. }

如何把 I love you 翻转成 you love I?
先全部翻转 uoy evol I
再每个词翻转

翻转怎么写？
此处输入图片的描述

Binary Search
-- Exclude half every time
1 四个要素

什么是routated sorted array
find minimal
find target
find median in two sorted array
为什么最坏是o(n)
find median 和 find kth
三步翻转

Sorted Array
-- If array is sorted, try binary search -- If array is not sorted, try sort it first


添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注