一些相似题目的小总结 - 从快排出发 - 《算法与数据结构🏹》

Image 1.png

在快排模板中我们会选择一个数，将两边分割。模板代码中的J在一次排序结束后，要么在分割数的前面一个，或者就是分割数本身，或者是后面一个
【X，Y，Q，D，J1，分割数(J2)，D(j3)，X，Y，Q，D】
J无论处在三个位置中的哪一个都可以，虽然J前面的数不是有序的，但他们一段都是小于某个数的K个数，将这小于某个数的K个数排好序后,注意啊，并不是X，Y，Q，D都一定有序，而是可能X，Y，Q，D中的一小段有序，比如下面的例子，第K个位置上的就是第K大或第K小的元素了

[2,2,3,1,4,66,35,98]
6
---快选结束之后，前6个数是这样的
[1,2,3,2,4,35]
前面这一段虽然没有序，但是一定都是小于35的，并且有一小段是连续的，
每次只递归排序一段区间，判断左右区间，不断逼近最后的K

剑指 Offer 40. 最小的k个数

和上一题一模一样，把前K个数取出来即可

75. 颜色分类

class Solution {
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    public void sortColors(int[] nums) {
        //l维护‘0’ r维护‘2’ cur维护‘1’
        int l = 0, r = nums.length - 1, cur = 0;
        while(cur <= r){
            if(nums[cur] == 2){
                swap(nums, cur, r);
                //cur++;换过来的不一定就是符合要求的1,有可能换了一个0过来
                r--;
            }else if(nums[cur] == 0){
                swap(nums, l, cur);
                //这里cur++是因为
                //这里从前面换过来的一定是1，不可能是2，是2的话肯定早就已经交换到后面去了
                cur++;
                l++;
            }else{
                cur++;
            }
        }
    }
}

148. 排序链表

这一题和上一题有点类似的地方是也用到了三个指针L,M,R，三个指针分别接受比我们选取的的一个数，小，相等，大的数。一轮之后，L链接的数都比M链接的小，R链接的都比M链接的大。
再递归递归排序L链接的左半边和R链接的右半边。等都排好之后，再都链接起来即可。

class Solution {
    public ListNode getTail(ListNode head){
        while(head.next != null) head = head.next;
        return head;
    }
    public ListNode getMid(ListNode head){
        ListNode f = head, s = head;
        while(f != null && f.next != null){
            f = f.next.next;
            s = s.next;
        }
        return s;
    }
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        //1. 定义三个子链表虚拟头节点及其队尾
        ListNode left = new ListNode(-1); ListNode ltail = left;
        ListNode mid = new ListNode(-1); ListNode mtail = mid;
        ListNode right = new ListNode(-1); ListNode rtail = right;
        //2. 遍历链表，放到对应的子链表上面去
       int val = getMid(head).val;
       for(ListNode p = head; p != null; p = p.next){
           if(p.val < val) {
               ltail.next = p; ltail = ltail.next;
           }else if(p.val == val){
               mtail.next = p; mtail = mtail.next;
           }else{
               rtail.next = p; rtail = rtail.next;
           }
       }
        //3. 将子链表结尾赋值为null
        ltail.next = null; mtail.next = null; rtail.next = null;
        //4. 分别递归排左右两边
        left.next = sortList(left.next);
        right.next = sortList(right.next);
        //5. 连接三个子链表
        getTail(left).next = mid.next;
        getTail(left).next = right.next;
        //6. 返回头节点
        return left.next;
    }  
}

324. 摆动排序 II

快选求中位数，以中位数分三路，然后在前半截和后半截间隔插入，间隔插入有一个公式，一般都想不到(((φ(◎ロ◎;)φ)))，所以这一题完成前面两部，即215和75的知识就够了

class Solution {
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    public int findMid(int[] nums, int l, int r, int k){
        if(l >= r) return nums[k];
        int i = l - 1, j = r + 1, x = nums[l + r >> 1];
        while(i < j){
            do i++; while(nums[i] < x);
            do j--; while(nums[j] > x);
            if(i < j) swap(nums, i, j);
        }
        if(k <= j) return findMid(nums, l, j, k);
        else return findMid(nums, j + 1, r, k);
    }
    public void threeWayPart(int[] nums, int mid){
        int l = 0, cur = 0, r = nums.length - 1;
        while(cur < r){
            if(nums[cur] > mid){
                swap(nums, cur, r);
                r--;
            }else if(nums[cur] < mid){
                swap(nums, cur, l);
                cur++;
                l++;
            }else{
                cur++;
            }
        }
    }
    public void wiggleSort(int[] nums) {
        int len = nums.length;
        int mid = findMid(nums, 0, len - 1, len / 2);
        //System.out.print(mid);
        threeWayPart(nums, mid);

        for(int x : nums){
            System.out.print(x + " ");
        }
    }
}

280. 摆动排序

nums[0] <= nums[1] >= nums[2] <= nums[3]…
因为这道题目可以等于，和324里面的nums[0] < nums[1] > nums[2] < nums[3]不一样
所以对于
用例：[1,2,1,2,1,2,1,2,1,1,1,2,2,2]
280因为可以等于，所以答案可以是[[1,2,1,2,1,2,1,2,1,1,1,2,2,2]
但是324没有等于所以答案必须是[1,2,1,2,1,2,1,2,1,2,1,2,1,2]
所以280可以有简便方法

class Solution {
     public void wiggleSort(int[] nums) {
        //在奇数位元素小于下一个数则互换，在偶数位元素大于下一个则互换
        for(int i = 0;i < nums.length-1;i++){
            //如果是奇数位
            if(i % 2 != 0 && nums[i] < nums[i+1]){
                swap(nums,i,i+1);
            }
            //如果是偶数位
            if(i % 2 == 0 && nums[i] > nums[i+1]){
                swap(nums,i,i+1);
            }
        }
    }

    private void swap(int[] nums,int lo,int hi){
        int tmp = nums[lo];
        nums[lo] = nums[hi];
        nums[hi] = tmp;
    }
}

215. 数组中的第K个最大元素

215这题也可以用堆来做，堆主要用下面的操作

建堆语法，默认小根堆
- PriorityQueue heap = new PriorityQueue<>();
- PriorityQueue heap = new PriorityQueue<>((v1,v2) -> v2 - v1);
添加 heap.offer(x)
删除 heap.poll()
取堆头 heap.peek()

获取堆的容量 heap.size()

class Solution {
  public int findKthLargest(int[] nums, int k) {
      PriorityQueue<Integer> heap = new PriorityQueue<>((v1,v2) -> v2 - v1);
      for(int x : nums){
          heap.offer(x);
      }
      //退出掉K - 1个元素
      for(int i = 0; i < k - 1; i++){
          heap.poll();
      }
      return heap.peek();
  }
}

class Solution {
  public int findKthLargest(int[] nums, int k) {
      PriorityQueue<Integer> heap = new PriorityQueue<>();
      for(int x : nums){
          heap.add(x);
          if(heap.size() > k){
              heap.poll();
          }
      }
      return heap.peek();
  }
}

23. 合并K个升序链表

这道链表题有一个做法就是利用堆来做

class Solution {
  public ListNode mergeKLists(ListNode[] lists) {
      PriorityQueue<ListNode> heap = new PriorityQueue<>((v1,v2) -> v1.val - v2.val);
      for(ListNode node : lists){
          //有可能给的链表头结点是一个空的，要判断一下
          if(node != null){
              heap.offer(node);
          }
      }
      ListNode dummy = new ListNode(-1); 
      ListNode cur = dummy;
      while(heap.size() != 0){
          ListNode minNode = heap.poll();
          //退一个，添一个
          if(minNode.next != null) heap.add(minNode.next);
          cur.next = minNode;
          cur = cur.next;
      }
      return dummy.next;
  }
}