数字排序问题

1. 【Find Kth max number in two sorted list——在两个有序列表里，找出第k大的数字】 hard 二分查找

private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }

以上是findKth的写法。如果问题是：寻找两个有序数组的中位数，可以在这个函数外面套一个调用的壳子

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
    return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;  
}

2. 【34. 在排序数组中查找元素的第一个和最后一个位置】 medium 二分查找

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target - 1);
        int rightIdx = binarySearch(nums, target) - 1;
        if (leftIdx <= rightIdx && nums[leftIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    // 循环实现二分，查找第一个大于 target 的数的下标
    public int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

3. 【162. 寻找峰值】 medium 二分查找
   峰值元素是指其值严格大于左右相邻值的元素。
   给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
   你可以假设 nums[-1] = nums[n] = -∞ 。

   
   截屏2021-11-28 上午11.06.37.png

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return 0;

        // 先特判两边情况
        if(nums[0] > nums[1]) return 0;
        if(nums[n - 1] > nums[n - 2]) return n - 1;

        int l = 0, r = n - 1;
        while(l <= r) {
            int mid = (l + r) / 2;

            // 当前为峰值
            if(mid >= 1 && mid < n - 1 && nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
                return mid;
            } else if(mid >= 1 && nums[mid] < nums[mid - 1]) {
                // 峰值在 mid 左侧
                r = mid - 1;
            } else if(mid < n - 1 && nums[mid] < nums[mid + 1]) {
                // 峰值在 mid 右侧
                l = mid + 1;
            }
        }
        return -1;
    }
};

4. 【 搜索旋转排序数组】 medium 二分查找
   问题：

   
   截屏2021-11-28 上午11.26.19.png
   

   解析：

   
   截屏2021-11-28 上午11.25.54.png

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

5. 【673. 最长递增子序列】 medium 动态规划
   给定一个未排序的整数数组，找到最长递增子序列的个数。(子序列：可以不挨着)
   O(N*N)

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}

6. 【674. 最长连续递增序列】 easy 数组问题、不用动态规划，贪心算法，O(n)

class Solution {
   public int findLengthOfLCIS(int[] nums) {
       int ans = 0;
       int n = nums.length;
       int start = 0;
       for (int i = 0; i < n; i++) {
           if (i > 0 && nums[i] <= nums[i - 1]) {
               start = i;
           }
           ans = Math.max(ans, i - start + 1);
       }
       return ans;
   }
}

7. 【334. 递增的三元子序列】 medium O(n)
   给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
   如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

class Solution {
public:
  bool increasingTriplet(vector<int>& nums) {
    int len = nums.size();
    if (len < 3) return false;
    int small = INT_MAX, mid = INT_MAX;
    for (auto num : nums) {
      if (num <= small) {
        small = num;
      } else if (num <= mid) {
        mid = num;
      } 
      else if (num > mid) {
        return true;
      }
    }
    return false;    
  }
};