Sorting and Searching easy系列题

  1. Merge Sorted Array(这个问题只真是火,链表里面有,归并排序里有,这边也有,不过这次的版本是不需要另建数据的版本,也算是有一点不一样,考虑的东西还是4个判断,只不顾过这道题的方法有个简单的技巧,值得留意)
  2. First Bad Version(找到true和false的临界点,算是有序的一种表现,最容易想到的是二分搜索的方法)

    Sorting and Searching middle系列题

    Sort Colors

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    
    class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p1 = 0, p2 = n - 1, index = 0;
        while (index <= p2) {//这边写错了
            if (nums[index] == 0) {
                nums[index] = nums[p1];//这边也写错了
                nums[p1] = 0;
                p1++;
            } else if (nums[index] == 2) {
                nums[index] = nums[p2];
                nums[p2] = 2;
                p2--;
                index--;//这个地方没有考虑到,
            }
            index++;
        }
    }
    }

    三种颜色的分类,想到的是三向切分的思想,设立中间元素,遍历的时候把小于他的都换到前面,大于他的都换到后面,等于自己的时候按兵不动。但是需要细细考虑,遍历的index与大小部分索引i,j的关系。尤其是循环截止条件和把大数交换后要对这个大数重新判断。(返回去看一下三向切分的具体实现)

    Top K Frequent Elements

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    
    class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Integer>[] bucket = new List[nums.length + 1];
        /*
         * 按照值的大小进行排序,不熟练啊卧槽,这个和桶排序是什么关系呀
         * */
        for (int key : map.keySet()) {
            int freq = map.get(key);
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(key);
        }
        /*
         * 按照值的大小进行弹出
         * */
        List<Integer> res = new ArrayList<>();
        for (int i = nums.length; i > 0 && res.size() < k; i--) {
            if (bucket[i] != null) {
                res.addAll(bucket[i]);
            }
        }
        return res;
    }
    }

    问题是问出现频率最K高的数字,那首先我得统计频率,这个是跑不掉了,然后因为这道题只需要前K高的数字,所以我首先想到的是优先级队列,因为优先级队列对求最大值有着不错的效率,之后我又想到优先级队列的存在的对象得是一个键值对,因为我需要根据值(频率的大小)找到相应的键输出。 但是我的算法效率并不是很高,所以之后去看了高效答案,他用的是一个桶排序,每个桶是一个ArrayList(有可能几个元素出现的频率是一样的),由于桶的数组是直接按照最坏情况考虑的,所以存在着一定的冗余,但好处是可以提供有序性,最后一次按照桶的逆序和要求k的大小,将相应的值填入到res中就可以得到答案。

    Kth Largest Element in an Array

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    
    public class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        quickSort(nums,0,n-1,n-k);
        return nums[n-k];
    }
    private void quickSort(int[] nums, int start, int end, int target){
        if (start>=end){
            return;
        }
        int mid = start  + (end - start)/2;
        int pivot = choosePivot(nums[mid], nums[start], nums[end]);
        int i = start;
        int j = end;
        while(i<=j) {
            while (nums[i] < pivot) {
                i++;
            }
            while (nums[j] > pivot) {
                j--;
            }
            if (i <= j) {
                if (nums[i] != nums[j]) {
                    swap(nums, i, j);
                }
                i++;
                j--;
            }
        }
        if(target <= i - 1){
            quickSort(nums, start, i - 1, target);
        }
        else{
            quickSort(nums, i, end, target);
        }
    }
    
    private int choosePivot(int a, int b, int c) {
        if(a > b){
            if(c > a){
                return a;
            }
            else if(c > b){
                return c;
            }
            else{
                return b;
            }
        }
        else{
            if(c > b){
                return b;
            }
            else if(c > a){
                return c;
            }
            else{
                return a;
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    }

    由于找指定大小的数字,其实就和排序差不多了,想到排序一般就快排和归并排序,快排的话还有些改进的算法(三向,去中位数哨兵等),归并的话也有些改进的算法(不用交换而是整体后移or不建立新的数组还是改用其他的)。这边我用是中位数改进快排。

    Find Peak Element

    看到这题,第一个想法自然是要找的数需要进行前后比较,但是最后的答案让我有点懵逼

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    
    class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        int left = 0, right = n-1;
        while(left<right){
            int mid = left + (right-left)/2;
            if (nums[mid]<nums[mid+1]){
                left = mid +1;
            }
            else{
                right = mid;
            }
        }
        return left;
    }
    }

    这道题最后的解法利用了二分搜索,但是改动了条件找到了区间峰值。TODO

    Search for a Range(TODO)

    这道题是在给定有序的情况下找到目标值的范围,找到其中一个值的想法倒是容易,用二分总是能找到,问题是找到一个后需要进行前后遍历,找到边界值

    Merge Intervals(TODO)

    区间合并,要把重叠的子数组合并成长数组

    Search in Rotated Sorted Array

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    
    class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            /*
            * 找到了就返回坐标
            * */
            if (nums[mid]==target){
                return mid;
            }
    
            /*
            * 大于左边的话,说明左边序列一定是递增的
            * */
            if (nums[mid]>=nums[left]){
                /*
                * 接着判断目标值是不是在递增区间之内
                * */
                if (target>=nums[left]&&target<nums[mid]){
                    right = mid - 1;
                }
                else{
                    left = mid + 1;
                }
            }
            else if(nums[mid]<nums[right]){
                if (target>nums[mid]&&target<=nums[right]){
                    left = mid + 1;
                }
                else{
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
    }

    两段有序数组之间找到目标值(无重复),有序数组找值自然想到二分,但是要处理有个分界点的问题,此处需要加入额外的条件进行区分

    Search a 2D Matrix II

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    
    class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m == 0) {
            return false;
        }
        int n = matrix[0].length;
        int row = 0;
        int col = n - 1;
        while (row < m && col >= 0) {
            int num = matrix[row][col];
            if (num == target) return true;
            if (num > target) {
                col--;
            } else {
                row++;
            }
        }
        return false;
    }
    }

    这道题的第一题是行有序,列有序,且行列之间前后也有序,那其实就是套用二分的模板,这边的第二题则行列之间有序性去除,但是从右上角的角度去观察的话,其实会发现这是一颗变相的二叉树,依次按照二分的思想去找依旧能和找到。

    Sorting and Searching hard系列题

    Wiggle Sort II(水平不够,完全没有思路)(TODO)

    Kth Smallest Element in a Sorted Matrix(TODO)

    Median of Two Sorted Arrays(TODO)

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    
    class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int len1 = 0;
            int len2 = 0;
            if (nums1 == null && nums2 == null){
                return 0.0;
            }
            else if (nums1 == null){
                len2 = nums2.length;
            }
            else if (nums2 == null){
                len1 = nums1.length;
            }
            else{
                len1 = nums1.length;
                len2 = nums2.length;
            }
            if ((len1+len2)%2 == 0){
                return (double) (findKth(nums1, 0 ,len1 , nums2, 0,len2, (len1+len2)/2)+findKth(nums1, 0 ,len1 , nums2, 0,len2, (len1+len2)/2+1))/2.0;
            }
            else{
                return (double) (findKth(nums1, 0 ,len1 , nums2, 0,len2, (len1+len2)/2+1));
            }
    
        }
        private int findKth(int[] nums1, int start1, int len1, int[] nums2, int start2, int len2, int k){
                
        /*
        * 统一为len1更小,方便处理
        * */
        if (len1>len2){
            return findKth(nums2, start2, len2, nums1, start1, len1, k);
        }
    
                
            /*
        * 循环结束条件
        * */
        if (len1 == 0){
            return nums2[start2+k-1];
        } 
            /*
             * 额外的循环结束条件
             * */
        if (k==1){
            return Math.min(nums1[start1],nums2[start2]);
        }  
        /*
        * 最核心的一般处理过程,包含divide
        * */
        int p1 = Math.min(len1, k/2);
        int p2 = k - p1;
        int n1 = nums1[start1+p1-1];
        int n2 = nums2[start2+p2-1];
        if (n1 == n2){
            return n1;
        }
        else if (n1<n2){
            return findKth(nums1, start1+p1 ,len1-p1 , nums2, start2,len2,k-p1);
        }
        else {
            return findKth(nums1, start1 ,len1 , nums2, start2+p2,len2-p2,k-p2);
        }
    }
    }

    最先想到的一种方法是先进行合并(这个是考过很多次的了),合并之后马上能找到中位数,但是这个方法时间复杂度不满足要求。实际的解法还是很复杂的,自己很难想到。