排序专题

[TOC]

75. 颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，请原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶：

• 一个直观的解决方案是使用计数排序的两趟扫描算法。
  首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
• 你能想出一个仅使用常数空间的一趟扫描算法吗？

题目解析

参考代码

• 使用双路快排的思想

        /*
          |------|---------| 0|------|---------------|
          |  0   |      1  | 1|      |   2           |
          |------|---------| 2|------|---------------|
                zero         i      two
        [0, zero] == 0
        [two , len - 1] == 2
        */
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int len = nums.size();
        int zero = -1;
        int two = len;
        for(int i = 0; i < two;)
        {
            if(nums[i] == 0)
            {
                swap(nums[++zero], nums[i++]);
            }
            else if(nums[i] == 1)
            {
                i++;
            }
            else if(nums[i] == 2)
            {
                swap(nums[--two], nums[i]);
            }
            else
            {
                assert(nums[i] == 0 || nums[i] == 1 || nums[i] == 2);
            }
        }   
    }
};

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

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

参考代码

class Solution {
public:
  int findKthLargest(vector<int>& nums, int k) {
      return findKthLargest(nums, 0, nums.size()-1, nums.size() -  k);
  }
  int findKthLargest(vector<int>& nums, int left, int right, int k)
  {
      int idx = partition(nums, left, right);
      if(idx == k)
          return nums[k];
      else if(idx > k)
          return findKthLargest(nums, left, idx-1, k);
      else
          return findKthLargest(nums, idx+1, right, k);
  }
  /*
  |---|--------|-----|---------------|----|--------|
  | v |   <v   | >=v |               | <v |   >=v  |
  |---|--------|-----|---------------|----|--------|
                  i                     j
  //[left+1, i) < v     nums[i] == v
  //(j, right]  >= v    nums[j] < v
  */
  int partition(vector<int>& nums, int left, int right)
  {
      swap(nums[left], nums[rand() % (right - left + 1) + left]);
      int v = nums[left];
      int i = left + 1;
      int j = right;
      while(1)
      {
          while(i <= right && nums[i] < v)
              i++;
          while(j >= left + 1 && nums[j] >= v) //这里有等号
              j--;
          if(i > j)
              break;
          swap(nums[i], nums[j]);
      }
      swap(nums[left], nums[j]);
      return j;
  }
};