Leetcode题解 剑指 Offer 40. 最小的k个数

PROBLEM

剑指 Offer 40. 最小的k个数

难度 简单

MY ANSWER

使用大顶堆，遍历到比堆顶小的元素时，出堆并将元素插入。priority_queue默认就为大顶堆，若构造小顶堆取相反数即可。时间复杂度为O(nlogk)，空间复杂度O(k)。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        priority_queue<int> heap;
        vector<int> res;
        if(arr.empty() || !k) {
            return res;
        }
        for(int i = 0; i < k; i++) {
            heap.push(arr[i]);
        }
        for(int i = k; i < arr.size(); i++) {
            if(arr[i] < heap.top()) {
                heap.pop();
                heap.push(arr[i]);
            }
        }
        while(heap.size()) {
            res.push_back(heap.top());
            heap.pop();
        }
        return res;
    }
};

BETTER SOLUTION

快排思路，划分直到pivot等于k为止，返回前面k个数。平均时间复杂度O(n)，最坏情况下时间复杂度为O(n^2)，空间复杂度O(logn)。

class Solution {
public:
    vector<int> arr;
    int k;
    void qselect(int left, int right) {
        int pivot = arr[left];
        int i = left, j = right;
        while(i < j) {
            while(arr[j] >= pivot && i < j) {
                j--;
            }
            while(arr[i] <= pivot && i < j) {
                i++;
            }
            swap(arr[i], arr[j]);
        }
        swap(arr[left], arr[i]);
        if(i < k) {
            qselect(i + 1, right);
        }
        if(i > k) {
            qselect(left, i - 1);
        }
        if(i == k) {
            return;
        }
    }
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(k >= arr.size()) {
            return arr;
        }
        this->arr = arr;
        this->k = k;
        vector<int> res;
        qselect(0, arr.size() - 1);
        for(int i = 0; i < k; i++) {
            res.push_back(this->arr[i]);
        }
        return res;
    }
};

SUMMARY

• priority_queue

• 堆模板：

  //小顶堆
  vector<int> arr;
  int heapsize;
  
  void init() {
      arr.push_back(INT_MIN);		//0存储最小值标志，堆从1开始
      heapsize = 0;
  }
  
  void push(int x) {		//加到末尾，上滤
      int i;
      arr.push_back(x);
      for(i = ++heapsize; arr[i/2] > x; i /= 2) {
          arr[i] = arr[i / 2];
      }
      arr[i] = x;
  }
  
  void pop() {		//最尾部节点放到堆顶,下滤
      int i, child;
      int min, last;
      min = arr[1];
      last = arr[heapsize--];
      for(i = 1; i * 2 <= heapsize; i = child) {
          child = i * 2;
          if(child != heapsize && arr[child+1] < arr[child]) {
              child++;
          }
          if(last > arr[child]) {
              arr[i] = arr[child];
          }
          else {
              break;
          }
      }
      arr[i] = last;
      arr.pop_back();
  }
  
  void buildheap(vector<int> tmp) {		//从第一个有儿子的节点开始逐个下滤
      arr = tmp;
      arr.insert(arr.begin(), INT_MIN);
      heapsize = tmp.size();
      for(int i = heapsize / 2; i > 0; i--) {
          int node, child;
          node = arr[i];
          int j;
          for(j = i; j * 2<= heapsize; j = child) {
              child = j * 2;
              if(child != heapsize && arr[child+1] < arr[child]) {
                  child++;
              }
              if(node > arr[child]) {
                  arr[j] = arr[child];
              }
              else {
                  break;
              }
          }
          arr[j] = node;
      }
  }
  
  int top() {
      return arr[1];
  }

• 快排模板：

  void quickSort(vector<int>& arr, int l, int r) {
          // 子数组长度为 1 时终止递归
          if (l >= r) return;
          // 哨兵划分操作（以 arr[l] 作为基准数）
          int i = l, j = r;
          while (i < j) {
              while (i < j && arr[j] >= arr[l]) j--;
              while (i < j && arr[i] <= arr[l]) i++;
              swap(arr[i], arr[j]);
          }
          swap(arr[i], arr[l]);
          // 递归左（右）子数组执行哨兵划分
          quickSort(arr, l, i - 1);
          quickSort(arr, i + 1, r);
      }
  };