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，同时输入只满足自顶向下和自左向右的升序，行与行之间不再有递增关系，与上题有较大区别。时间复杂度为线性要求，因此可从元素排列特点出发，从一端走向另一端无论如何都需要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.

thinking