给出一个整数数组，输出最小的k个数。

  • 采用快速选择算法

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

  1. class Solution {
  2.     int partition(vector<int>& nums, int l, int r) {
  3.         int pivot = nums[r];
  4.         int i = l - 1;
  5.         for (int j = l; j <= r - 1; ++j) {
  6.             //从l到r-1遍历数组，发现小于pivot的数，放到左边
  7.             if (nums[j] <= pivot) {
  8.                 //待交换位置向前移动
  9.                 i = i + 1;
  10.                 swap(nums[i], nums[j]);
  11.             }
  12.         }
  13.         //将pivot放在他该放的位置
  14.         swap(nums[i + 1], nums[r]);
  15.         //返回排序好的位置
  16.         return i + 1;
  17.     }
  18.     // 基于随机的划分
  19.     int randomized_partition(vector<int>& nums, int l, int r) {
  20.         //生成[l,r]之间的随机数
  21.         int i = rand() % (r - l + 1) + l;
  22.         //将l和r交换位置
  23.         //方便函数的编写，每次默认pivot是r
  24.         swap(nums[r], nums[i]);
  25.         return partition(nums, l, r);
  26.     }
  27.     void randomized_selected(vector<int>& arr, int l, int r, int k) {
  28.         if (l >= r) return;
  29.         //划分之后只能得到是第k小的数，但数据并非有序
  30.         int pos = randomized_partition(arr, l, r);
  31.         //当前区域内有多少个数
  32.         int num = pos - l + 1;
  33.         if (k == num) return;
  34.         else if (k < num) randomized_selected(arr, l, pos - 1, k);
  35.         else randomized_selected(arr, pos + 1, r, k - num);   
  36.     }
  37. public:
  38.     vector<int> getLeastNumbers(vector<int>& arr, int k) {
  39.         //初始化seed函数
  40.         srand((unsigned)time(NULL));
  41.         randomized_selected(arr, 0, (int)arr.size() - 1, k);
  42.         vector<int>vec;
  43.         for (int i = 0; i < k; ++i) vec.push_back(arr[i]);
  44.         return vec;
  45.     }
  46. };

水壶问题

  1. using PII = pair<int, int>;
  3. class Solution {
  4. public:
  5.     bool canMeasureWater(int x, int y, int z) {
  6.         stack<PII> stk;
  7.         //和push类似，更高效
  8.         stk.emplace(0, 0);
  9.         //定义hash函数，将pair的first和second进行异或
  10.         auto hash_function = [](const PII& o) {return hash<int>()(o.first) ^ hash<int>()(o.second);};
  11.         //将pair和hash值进行关联
  12.         unordered_set<PII, decltype(hash_function)> seen(0, hash_function);
  13.         while (!stk.empty()) {
  14.             //判断stk中是否已经有元素
  15.             if (seen.count(stk.top())) {
  16.                 stk.pop();
  17.                 continue;
  18.             }
  19.             seen.emplace(stk.top());
  20.             //将remain取出来
  21.             auto [remain_x, remain_y] = stk.top();
  22.             stk.pop();
  23.             if (remain_x == z || remain_y == z || remain_x + remain_y == z) {
  24.                 return true;
  25.             }
  26.             // 把 X 壶灌满。
  27.             stk.emplace(x, remain_y);
  28.             // 把 Y 壶灌满。
  29.             stk.emplace(remain_x, y);
  30.             // 把 X 壶倒空。
  31.             stk.emplace(0, remain_y);
  32.             // 把 Y 壶倒空。
  33.             stk.emplace(remain_x, 0);
  34.             // 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
  35.             stk.emplace(remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y));
  36.             // 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
  37.             stk.emplace(remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x));
  38.         }
  39.         return false;
  40.     }
  41. };
  43. 作者：LeetCode-Solution
  44. 链接：https://leetcode-cn.com/problems/water-and-jug-problem/solution/shui-hu-wen-ti-by-leetcode-solution/
  45. 来源：力扣（LeetCode）
  46. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。