数组理论基础

@Date 2023-06-07
@Author Svetlana

1. 二分查找

   • 前置知识 区间查找的两种写法

     • 写法1
       • 左闭右毕 用在求x是否在区间中

         left = 0
         right = n - 1
         while left <= right:
             if nums[mid] > x:
                 right = mid - 1
             else if nums[mid] > x:
                 left = mid + 1
             else:
                 return mid
         return -1
         

     • 写法2
       • 左闭右开用在找第一个大于或小于x的下标

         left = 0
         right = n
         while left < right:
             if nums[mid] > x:
                 right = mid
             else if: nums[mid] > x:
                 left = mid + 1
             else return mid
         return -1
         

   • LeetCode 704

     class Solution {
         public int search(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 - 1;
                 else if (nums[mid] < target) l = mid + 1;
                 else return mid;
             }
             return -1;
         }
     }
     

     class Solution {
         public int search(int[] nums, int target) {
             // 左闭右开版本
             int l = 0, r = nums.length;
             while (l < r) {
                 int mid = l + r >> 1;
                 if (nums[mid] > target) r = mid;
                 else if (nums[mid] < target) l = mid + 1;
                 else return mid;
             }
             return -1;
         }
     }
     

   • LeetCode 35

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

   • LeetCode 34

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

2. 移除元素

   • LeetCode 27

     class Solution {
         public int removeElement(int[] nums, int val) {
             int j = 0;
             for (int i = 0; i < nums.length; i++) {
                 if (nums[i] != val)
                     nums[j++] = nums[i];
             }
             return j;
         }
     }