Before we look at LeetCode, let’s look at portal sorting:

1122. Relative sort of arrays

I give you two arrays, arr1 and arR2,

  • arr2The elements in the
  • arr2Each element in thearr1 中

Sort the elements in ARR1 so that the relative order of the items in ARR1 is the same as that in ARR2. Elements that do not appear in ARR2 need to be placed at the end of ARR1 in ascending order.

Example:

Input: arr1 =,3,1,3,2,4,6,7,9,2,19 [2], arr2 =,1,4,3,9,6 [2] output:,2,2,1,4,3,3,9,6,7,19 [2]Copy the code

Tip:

  • arr1.length, arr2.length <= 1000
  • 0 <= arr1[i], arr2[i] <= 1000
  • arr2The elements in thearr2[i]Each are not identical
  • arr2Each element inarr2[i]inarr1 中

Solution: counting sort

  • Here can be used for reference the idea of counting sort, unclear children’s shoes can refer to the surface of the link.

    1. Buckets = ARr1 [I], buckets = arr1[I] number of occurrences –> buckets are in order (bucket number is increasing)

    2. Into sorted array (ANS) : According to ARR2, the buckets are taken out in turn into sorted array; And then the bucket element — until the bucket runs out

      Note: Unlike counting sort, which requires summing to get subscripts. And the order here is not 1-1001, it has its own order, so you can just pull it out directly

      –> General counting sort can also be traversed through 1-n, but if n is too large, the time state is complex, so in advance to calculate the index

    3. Residual processing: take out the elements that do not appear in ARR2 bucket by bucket

  • Complexity:

    • Time: O (n)
    • Space: O (n)
public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] buckets = new int[1001];
        int[] ans = new int[arr1.length];
    	/ / 1. Into the barrel
        for (int i = 0; i < arr1.length; i++) {
            buckets[arr1[i]]++;
        }  
        int idx = 0;
    	// 2. Enter the sorted array
        for (int i = 0; i < arr2.length; i++) {
            while (buckets[arr2[i]] > 0) { ans[idx++] = arr2[i]; buckets[arr2[i]]--; }}// 3. Residual processing
        for (int i = 0; i < 1001; i++) {
            while (buckets[i] > 0) { ans[idx++] = i; buckets[i]--; }}return ans;
}
Copy the code

56. Merge interval ²

Given a set of intervals, merge all overlapping intervals.

Example 1:

Input: [[1, 3], [2, 6], [8, 10], [15, 17]] output: [[1, 6], [8, 10], [15, 17]] : interval [1, 3] and [2, 6] overlap, merge them into [1, 6].Copy the code

Example 2:

Input: [[1, 4], [4, 5]] output: [[1, 5]] : interval [1, 4] and [4, 5] can be seen as overlapping range.Copy the code

Solution: sort + double pointer

  • Create a merge based on start and end
    1. Sort: Sort these arrays by their first element; Sort a two-dimensional Array by array. sort requires a comparator
    2. Initial intervals: Save the initial intervals[0] (start, end)
    3. Create interval:
      • If the current interval start <= current end, then the current interval can be combined with the previous interval; Update the end
      • If the current interval start > current end, create a new interval; Update start and end after creation
    4. Residual processing: Create the last interval
public int[][] merge(int[][] intervals) {
    	List
      
       ;
      []>
    	// List#add is handy; But toArray(new int[0][]) is returned to a two-dimensional array
        List<int[]> res = new ArrayList<>();
        if(intervals.length == 0 || intervals == null) return res.toArray(new int[0] []);/ / 1. Sorting
    	// Use lamada to implement Comptor interface; Represents comparing two one-dimensional arrays i1, i2 compared by I [0]
        Arrays.sort(intervals, (i1, i2) -> i1[0] - i2[0]);
    	// 2. Initial interval
        int start = intervals[0] [0], end = intervals[0] [1];
    	// 3. Create a range
        for (int[] arr : intervals) {
            if (arr[0] <= end) {
                end = Math.max(end, arr[1]);
            } else {
                res.add(new int[]{start, end});
                start = arr[0];
                end = arr[1]; }}// 4. Residual processing
        res.add(new int[]{start, end});
        return res.toArray(new int[0] []); }Copy the code