lintcode: (60) Search Insert Position
Problem Statement
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.
Example
[1,3,5,6] , 5 → 2
[1,3,5,6] , 2 → 1
[1,3,5,6] , 7 → 4
[1,3,5,6] , 0 → 0
Challenge
O(log(n)) time
這個題其實就是找lower bound。
代碼如下：
public class Main {
public static void main(String[] args) {
int size = 4;
ArrayList list = new ArrayList();
list.add(1);
list.add(3);
list.add(5);
list.add(6);
System.out.println(solve(list,5)); //print 2
System.out.println(solve(list,2)); //print 1
System.out.println(solve(list,7)); //print 4
System.out.println(solve(list,0)); //print 0
}
public static int solve(ArrayList list, int target){
if(list.size()==0||list==null){
return 0;
}
int start = -1;
int end = list.size();
int mid;
while(start+1<end){
mid = start+(end-start)/2;
if((int)list.get(mid)==target){
return mid;
}else{
if((int)list.get(mid)<target){
start = mid;
}else{
end = mid;
}
}
}
return start+1;
}
}
leetcode: 34 Search for a Range
Problem
Given an array of integers 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].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
解題思路：
這題和Search Insert Position相似，唯一的是，當mid==target時要左右搜索邊界，且搜索邊界的時候注意數組不要越界
代碼如下：
public int[] searchRange(int[] nums, int target) {
int array[] = new int[2];
array[0]=-1;
array[1]=-1;
if(nums.length==0||nums==null){
return array;
}
int start = -1;
int end = nums.length;
int mid;
while(start+1<end){
mid = start+(end-start)/2;
if(nums[mid]==target){
int left= mid;
int right = mid;
while(right<nums.length&&nums[right]==target){
right++;
}
while(left>=0&&nums[left]==target){
left--;
}
array[0]=left+1;
array[1]=right-1;
return array;
}else{
if(nums[mid]<target){
start = mid;
}else{
end = mid;
}
}
}
return array;
}
這個題還有另一種思路，分兩次搜索，一次搜索upper bound，一次搜索lower bound
代碼如下：
public int[] searchRange(int[] A, int target) {
int[] result = new int[]{-1, -1};
if (A == null || A.length == 0) return result;
int lb = -1, ub = A.length;
// lower bound
while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (A[mid] < target) {
lb = mid;
} else {
ub = mid;
}
}
// whether A[lb + 1] == target, check lb + 1 first
if ((lb + 1 < A.length) && (A[lb + 1] == target)) {
result[0] = lb + 1;
} else {
result[0] = -1;
result[1] = -1;
// target is not in the array
return result;
}
// upper bound, since ub >= lb, we do not reset lb
ub = A.length;
while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (A[mid] > target) {
ub = mid;
} else {
lb = mid;
}
}
// target must exist in the array
result[1] = ub - 1;
return result;
}
lintcode: (74) Search a 2D Matrix
代碼如下：
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length==0||matrix==null){
return false;
}
int start = -1;
int m=matrix.length;
int n=matrix[0].length;
int end = m*n;
while(start+1<end){
int mid = start+(end-start)/2;
if(matrix[mid/n][mid%n]==target){
return true;
}else{
if(matrix[mid/n][mid%n]<target){
start = mid;
}else{
end = mid;
}
}
}
if((start>=0&&matrix[start/n][start%n]==target)||(end<m*n&&matrix[end/n][end%n]==target)){
return true;
}
return false;
}
leetcode 240 search a 2D matrix 2
Problem Statement
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.
Example
Consider the following matrix:
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]
Given target = 3, return 2.
Challenge
O(m+n) time and O(1) extra space
題解 - 自右上而左下
1.復雜度要求——O(m+n) time and O(1) extra space，同時輸入只滿足自頂向下和自左向右的升序，行與行之間不再有遞增關系，與上題有較大區(qū)別。時間復雜度為線性要求，因此可從元素排列特點出發(fā)，從一端走向另一端無論如何都需要m+n步，因此可分析對角線元素。
2.首先分析如果從左上角開始搜索，由于元素升序為自左向右和自上而下，因此如果target大于當前搜索元素時還有兩個方向需要搜索，不太合適。
3.如果從右上角開始搜索，由于左邊的元素一定不大于當前元素，而下面的元素一定不小于當前元素，因此每次比較時均可排除一列或者一行元素（大于當前元素則排除當前行，小于當前元素則排除當前列，由矩陣特點可知），可達到題目要求的復雜度。
Code:
public int searchMatrix(int[][] matrix, int target) {
int occurrence = 0;
if (matrix == null || matrix[0] == null) {
return occurrence;
}
int row = 0, col = matrix[0].length - 1;
while (row >= 0 && row < matrix.length && col >= 0 && col < matrix[0].length) {
if (matrix[row][col] == target) {
occurrence++;
col--;
} else if (matrix[row][col] > target) {
col--;
} else {
row++;
}
}
return occurrence;
}
leetcode 162 find pink element
problem:
A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
click to show spoilers.
