LC33. 搜索旋转排序数组

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        // int[] nums = {4, 5, 6, 7, 0, 1, 2}; 
        // int target = 0; // 4
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 3; // -1

        int res = search(nums, target);
        System.out.println(res); 
    }


    public static int search(int[] nums, int target) {
       if (nums.length == 0) return -1;
       int l = 0, r = nums.length - 1;
       while (l < r) {
           int mid = l + r + 1 >> 1;
           if (nums[mid] >= nums[0]) l = mid;
           else r = mid - 1;
       }

       if (target >= nums[0]) l = 0;
       else {
            l = r + 1;   
            r = nums.length - 1;
       }

       while (l < r) {
           int mid = l + r >> 1;
           if (nums[mid] >= target) r = mid;
           else l = mid + 1;
       }

       if (nums[r] == target) return r;
       return -1;
    }
}

LC34. 在排序数组中查找元素的第一个和最后一个位置

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {5, 7, 7, 8, 8, 10}; 
        int target = 8; // 3, 4

        // int[] nums = {5, 7, 7, 8, 8, 10}; 
        // int target = 6; // -1 -1

        int[] res = searchRange(nums, target);
        for (int i : res) {
            System.out.print(i);
            System.out.print(" ");
        }
        System.out.println(); 
    }


    public static int[] searchRange(int[] nums, int target) {
       if (nums.length == 0) return new int[]{-1, -1};
       int l = 0, r = nums.length - 1;
       while (l < r) {
           int mid = l + r >> 1;
           if (nums[mid] >= target) r = mid;
           else l = mid + 1;
       }

       if (nums[r] != target) return new int[]{-1, -1};
       int L = r;
       l = 0; r = nums.length - 1;

       while (l < r) {
           int mid = l + r + 1 >> 1;
           if (nums[mid] <= target) l = mid;
           else r = mid - 1;
       }

       return new int[]{L, r};
    }
}

LC35. 搜索插入位置

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {1, 3, 5, 6}; 
        int target = 5; // 2

        // int[] nums = {1, 3, 5, 6}; 
        // int target = 2; // 1

        int res = searchInsert(nums, target);
        System.out.println(res); 
    }


    public static int searchInsert(int[] nums, int target) {
       int l = 0, r = nums.length - 1;
       while (l < r) {
           int mid = l + r >> 1;
           if (nums[mid] >= target) r = mid;
           else l = mid + 1;
       }

       return l;
    }
}

LC74. 搜索二维矩阵

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[][] matrix = {
            {1, 3, 5, 7},
            {10, 11, 16, 20},
            {23, 30, 34, 50}
        }; 

        int target = 3;

        boolean res = searchMatrix(matrix, target);
        System.out.println(res);  // true
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return false;
        int n = matrix.length, m = matrix[0].length;
        int l = 0, r = n * m - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (matrix[mid / m][mid % m] >= target) r = mid;
            else l = mid + 1;
        }

        return matrix[r / m][r % m] == target;
    }
}

LC81. 搜索旋转排序数组II

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {2, 5, 6, 0, 0, 1, 2}; 
        int target = 0; // true

        // int[] nums = {2, 5, 6, 0, 0, 1, 2}; 
        // int target = 3;

        boolean res = search(nums, target);
        System.out.println(res);  // false
    }

    public static boolean search(int[] nums, int target) {
        if (nums.length == 0) return false;
        int R = nums.length - 1;
        while (R >= 0 && nums[R] == nums[0]) R --;

        if (R < 0) return nums[0] == target;

        int l = 0, r = R;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }

        if (target >= nums[0]) {
            r = l; l = 0;
        } else {
            l ++;
            r = R;
        }

        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        return nums[r] == target;
    }
}

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

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {3, 4, 5, 1, 2}; // 1

        // int[] nums = {4, 5, 6, 7, 0, 1, 2}; // 0

        int res = findMin(nums);
        System.out.println(res); 
    }


    public static int findMin(int[] nums) {
       int l = 0, r = nums.length - 1;
       if (nums[r] >= nums[l]) return nums[0];

       while (l < r) {
           int mid = l + r >> 1;
           if (nums[mid] < nums[0]) r = mid;
           else l = mid + 1;
       }

       return nums[r];
    }
}

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

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {1, 3, 5}; // 1

        // int[] nums = {2, 2, 2, 0, 1}; // 0

        int res = findMin(nums);
        System.out.println(res); 
    }


    public static int findMin(int[] nums) {
       int l = 0, r = nums.length - 1;
       while (l < r && nums[r] == nums[0]) r --;
       if (nums[l] <= nums[r]) return nums[0];

       while (l < r) {
           int mid = l + r >> 1;
           if (nums[mid] < nums[0]) r = mid;
           else l = mid + 1;
       }

       return nums[r];
    }
}

LC162. 寻找峰值

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {1, 2, 3, 1}; // 2

        // int[] nums = {1, 2, 1, 3, 5, 6, 4}; // 1或5

        int res = findPeakElement(nums);
        System.out.println(res); 
    }


    public static int findPeakElement(int[] nums) {
       int l = 0, r = nums.length - 1;

       while (l < r) {
           int mid = l + r >> 1;
           if (nums[mid] > nums[mid + 1]) r = mid;
           else l = mid + 1;
       }

       return r;
    }
}

LC240. 搜索二维矩阵II

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[][] matrix  = {
            {1, 4, 7, 11, 15},
            {2, 5, 8, 12, 19},
            {3, 6, 9, 16, 22},
            {10, 13, 14, 17, 24},
            {18, 21, 23, 26, 30}
        }; 
        // int target = 5; // true
        int target = 20; // false

        boolean res = searchMatrix(matrix, target);
        System.out.println(res);  // false
    }
    // 方法一：二分O(nlogm)
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return false;
        int n = matrix.length, m = matrix[0].length;
        for (int i = 0; i < n; i ++) {
            int l = 0, r = m - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (matrix[i][mid] <= target) l = mid;
                else r = mid - 1;
            }

            if (matrix[i][l] == target) return true;
        }

        return false;
    }
    /*
    // 方法二：从右上角出发 O(N + M)
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return false;
        int n = matrix.length, m = matrix[0].length;
        int i = 0, j = m - 1;
        while (i < n && j >= 0) {
            int t = matrix[i][j];
            if (t == target) return true;
            else if (t > target) j --;
            else i ++;
        }

        return false;
    }
    */
}

LC274. H指数

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] citations  = {3, 0, 6, 1, 5}; 

        int res = hIndex(citations);
        System.out.println(res);  // 3
    }

    // 方法一： 从小到大排的写法
    public static int hIndex(int[] c) {
        Arrays.sort(c);

        int res = 0, n = c.length;
        for (int i = 0; i < n; i ++) 
            if (c[i] >= n - i) {
                res = n - i;
                break;
            }
        return res;
    }

    /* 
    // 方法二：从大到小排
    public static int hIndex(int[] c) {
        Arrays.sort(c);
        for (int i = 0, j = c.length - 1; i < j; i ++, j --) {
            int tmp = c[i];
            c[i] = c[j];
            c[j] = tmp;
        }

        for (int h = c.length; h >= 0; h --) 
            if (c[h - 1] >= h)
                return h;
        return 0;
    }
    */
}

LC275. H指数II

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] citations  = {3, 0, 6, 1, 5}; 

        int res = hIndex(citations);
        System.out.println(res);  // 3
    }

    public static int hIndex(int[] c) {
        int n =c.length;
        int l = 0, r = n;

        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (c[n - mid] >= mid) l = mid;
            else r = mid - 1;
        }

        return r;
    }

}

AC14. 不修改数组找出重复的数字

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int[] nums = {1, 3, 4, 2, 2};   // 2
        // int[] nums = {3, 1, 3, 4, 2};   // 3

        int res = findDuplicate(nums);
        System.out.println(res);
    }

    // 方法一：二分，时间O(NlogN)
    public static int findDuplicate(int[] nums) {
        int l = 1, r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            int s = 0;
            for (int x : nums)
                if (x >= l && x <= mid)
                    s ++;

            if (s > mid - l + 1) r = mid;
            else l = mid + 1;
        }

        return r;
    }

   /* 
    // 方法二：环形链表思路，时间O(N) 
    public static int findDuplicate(int[] nums) {
        int a = 0, b = 0;
        while (true) {
            a = nums[a];
            b = nums[nums[b]];
            if (a == b) {
                a = 0;
                while (a != b) {
                    a = nums[a];
                    b = nums[b];
                }
                return a;
            }
        }
    }*/

/*    // 方法三：桶排序
    public static int findDuplicate(int[] nums) {
        int[] a = new int[10001];
        for (int i = 0; i < nums.length; i ++) a[nums[i]] ++;
        for (int i = 0; i < nums.length; i ++) 
            if (a[i] > 1) return i;

        return -1;
    }*/
}

AC22. 旋转数组的最小数字 (同~LC154. 寻找旋转排序数组中的最小值 II)

AC67. 数字在排序数组中出现的次数

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {1, 2, 3, 3, 3, 3, 4, 5}; 
        int k = 3;    

        int res = getNumberOfK(nums, k);
        System.out.println(res);  // 4
    }


     public static int getNumberOfK(int[] nums, int k) {
        if (nums.length == 0) return 0;
        int l = 0, r = nums.length - 1;

        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= k) r = mid;
            else l = mid + 1;
        }

        if (nums[r] != k) return 0;

        int left = l;
        l = 0; r = nums.length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= k) l = mid;
            else r = mid - 1;
        }

        return r - left + 1;
    }
}

AC68. 0到n-1中缺失的数字

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {0, 1, 2, 4}; 

        int res = getMissingNumber(nums);
        System.out.println(res);  // 3
    }

    /*     
    // 方法1：O(N)循环从1到最后一个数，如果缺一个数字，则break
    public static int getMissingNumber(int[] nums) {
        int i = 0;
        for (i = 0; i < nums.length; i ++) {
            if (nums[i] != i) break;
        }

        return i;
    }
    */

    /*   
    // 方法2:O(N)等差数列求和公式
    public static int getMissingNumber(int[] nums) {
        int n = nums.length;
        int res = n * (n + 1) / 2;
        for (int x : nums) res -= x;
        return res;
    }
    */

    // 方法3：O(logN)二分
    public static int getMissingNumber(int[] nums) {
        if (nums.length == 0) return 0;
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] != mid) r = mid;
            else l = mid + 1;
        }

        if (nums[r] == r) r ++;
        return r;
    }
}

AC69. 数组中数值和下标相等的元素

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {-3, -1, 1, 3, 5}; 

        int res = getNumberSameAsIndex(nums);
        System.out.println(res);  // 3
    }

    public static int getNumberSameAsIndex(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= mid) r = mid;
            else l = mid + 1;
        }

        if (nums[r] == r)  return nums[r];
        return -1;
    }
}