[Leetcode][Sort]排序相关题目汇总/分析/总结

目录

• 215 Kth Largest Element in an Array
• 34 Find First and Last Position of Element in Sorted Array
• 35 Search Insert Position
• 74 Search a 2D Matrix
• 164 Maximum Gap
• 179 Largest Number
• 220 Contains Duplicate III
• 242
• 315
• 327
• 349
• 350
• 493
• 524
• 710
• 767
• 853
• 922
• 969
• 973
• 976
• 1030
• 1054
• 1122

---

#215 Kth Largest Element in an Array

• Sol Quick Select

    public int findKthLargest(int[] nums, int k) {
        return help(nums, 0, nums.length-1, k);
    }
    public int help(int[] nums, int s, int e, int k){
        if(s >= e) return nums[s];
        int mid = (s+e) / 2;
        int pivot = nums[mid];
        int i = s, j = e;
        while(i <= j){
            while(i <= j && nums[i] > pivot) i++;
            while( i <= j && nums[j] < pivot) j--;
            if( i <= j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                i++;
                j--;
            }
        }
        //s..j,i..e
        if(j - s + 1 >=k ) return help(nums, s, j, k);
        if(i - s + 1 <= k) return help(nums, i, e, k - (i - s));
        return nums[j+1];
    }

Time: O(n)
T(N) =n +n/2+n/4+n/8+n/2^k = n*(1-2^-k)/(1-2-1) =2N
Space: O(logn)

#34 Find First and Last Position of Element in Sorted Array

• Sol Binary Search

    int[] res;
    public int[] searchRange(int[] nums, int target) {
        res = new int[]{-1, -1};
        help(nums, target, 0, nums.length-1);
        return res;
    }
    public void help(int[] nums, int target, int s, int e){
        if(s > e) return;
        int mid = (s+e) / 2;
        if(nums[mid] == target){
            if(res[0] == -1){
                res[0] = mid;
                res[1] = mid;
            }else{
                res[0] = res[0] < mid ? res[0] : mid;
                res[1] = res[1] > mid ? res[1] : mid;
            }
            help(nums, target, mid+1, e);
            help(nums, target, s, mid-1);
        }
        else if(nums[mid] < target) help(nums, target, mid+1, e);
        else if(nums[mid] > target) help(nums, target, s, mid-1);
    }

Time: O(logn)
Space: O(1)

#35 Search Insert Position

• Sol Binary Search

public int searchInsert(int[] nums, int target) {
        if(nums.length == 0) return 0;
        int i = 0, j = nums.length-1;
        while(i <= j){
            int mid = (i+j) / 2;
            if(nums[mid] == target){
                return mid;
            }
            if(nums[mid] < target){
                i = mid+1;
            }else{
                j = mid - 1;
            }
        }
        return i;
    }

Time O(logn)
Space O(1)

#74 Search a 2D Matrix

• Sol Binary Search

public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0) return false;
        int start = 0, rows = matrix.length, cols = matrix[0].length;
        int end = rows * cols - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(matrix[mid / cols][mid % cols] == target) return true;
            if(matrix[mid / cols][mid % cols] < target){
                start = mid+1;
            }else{
                end = mid-1;
            }
        }
        return false;
    }

Time O(logn)
Space O(1)

#164 Maximum Gap

• Sol Bucket Sort
  --bucket size:
  buckect_size = (max - min) / (len(nums) - 1)
  --bucket number:
  bucket_number = (max - min) / buckect_size + 1
  --each bucket
  ith bucket range: [min + i * b, min + (i+1) * b)
  put each num into bucket j : j = (num - min) / buckect_size
  --compare
  each bucket

public int maximumGap(int[] nums) {
        if(nums.length < 2) return 0;
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for(int num : nums){
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        int buck_size = Math.max(1, (max - min) / (nums.length - 1));
        int buck_num = (max - min) / buck_size + 1;
        int[][] buckets = new int[buck_num][3];
        for(int i = 0; i < buck_num; i++){
            buckets[i][0] = Integer.MAX_VALUE;
            buckets[i][1] = Integer.MIN_VALUE;
        }
        for(int num : nums){
            int j = (num - min) / buck_size;
            buckets[j][0] = Math.min(buckets[j][0], num);
            buckets[j][1] = Math.max(buckets[j][1], num);
            buckets[j][2] = 1;
        }
        int res = 0;
        int pre_min = min;
        for(int[] buc : buckets){
            if(buc[2] != 1) continue; 
            res = Math.max(res, buc[0] - pre_min);
            pre_min = buc[1];
        }
        return res;
    }

#179 Largest Number

• Sol Arrays.Sort + String compare
  String a, b
  a+b > b+a
  注意00的情况

public String largestNumber(int[] nums) {
        String[] str = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            str[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(str, (String o1, String o2) -> (o2+o1).compareTo(o1 + o2));
        if(str[0].equals("0")) return "0";
        String largestNumberStr = new String();
        for (String numAsStr : str) {
            largestNumberStr += numAsStr;
        }
        return largestNumberStr;
    }

Time O(nlogn)
Space O(1)

• Sol Merge Sort

#220 Contains Duplicate III

• Sol TreeSet

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<>();
        for(int i = 0; i < nums.length; i++){
            if(set.floor(new Long(nums[i]) + new Long(t)) != null && set.floor(new Long(nums[i]) + new Long(t)) >= new Long(nums[i])-new Long(t))
                return true;
            set.add(new Long(nums[i]));
            if(i >= k) set.remove(new Long(nums[i-k]));
        }
        return false;
    }

O(n log n)