& arr, int k) {vector myVector;quickSort(arr, 0, arr.size() - 1);while (k--) {myVector.push_back(arr[k]);}return myVector;}private:void quickSort(vector& arr, int left, int right) {if (left >= right) {return;}int tempLeft = left;int tempRight = right;int base = arr[tempLeft]; //最左边元素作为基准元素while (tempLeft < tempRight) {//从右往左扫描，找到第一个比基准元素小的元素while (tempRight > tempLeft && arr[tempRight] >= base) {tempRight--;}//从左往右扫描，找到第一个比基准元素大的元素while (tempLeft < tempRight && arr[tempLeft] <= base) {tempLeft++;}//找到这种元素arr[tempLeft]后，与arr[tempRight]交换if (tempLeft < tempRight) {swap(arr[tempLeft], arr[tempRight]);}}//基准元素归位arr[left] = arr[tempLeft];arr[tempLeft] = base;quickSort(arr, left, tempLeft - 1); //对基准元素左边的元素进行递归排序quickSort(arr, tempLeft + 1, right); //对基准元素右边的进行递归排序}};
方法一：offer转移法，直接排序，返回前k个 。
方法二：使用大根堆即根为最大数，队列中先存入k个元素，然后再使用数组剩下的元素与队头进行比较，因为要最小的k个，所以队头比数组元素大了才进行操作，出队，入队新元素，最终再将这个队列中的元素存入返回数组，就完成了 。
方法三：快排 。
剑指 Offer 41. 数据流中的中位数
![在这里插入
class MedianFinder {public:/** initialize your data structure here. */priority_queue, less> smallQueue; //从大到小排序priority_queue, greater> bigQueue; //从小到大排序int n;MedianFinder() {n = 0;}void addNum(int num) {if (smallQueue.empty()) {smallQueue.push(num);n++;return;}if (smallQueue.top() > num) {smallQueue.push(num);} else {bigQueue.push(num);}n++;if (smallQueue.size() - bigQueue.size() == 2) {bigQueue.push(smallQueue.top());smallQueue.pop();}if (bigQueue.size() - smallQueue.size() == 2) {smallQueue.push(bigQueue.top());bigQueue.pop();}}double findMedian() {if (n % 2) {if (smallQueue.size() > bigQueue.size()) {return (double)smallQueue.top();} else {return (double)bigQueue.top();}} else {return (double)(smallQueue.top() + bigQueue.top()) / 2;}}};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/
看不懂看不懂，直接就是一个双顶对冲，一个大根堆一个小根堆（大根堆就是堆顶是最大的数，小根堆就是堆顶是最小的数），等于说是把存入的数据从中间砍成两半，小根堆里存储都是大于大根堆顶的数，大根堆存储都是小于小根堆堆顶的数，那么这两个数中间就是整体数据的中间，那么我们只需要再判断是偶数个数据还是奇数个数据就好，奇数个就返回两个根堆size大的那个堆顶，偶数个就返回两个顶之和除以2，那么我们就只需要再使用一个数据存储总数据的个数就行了 。输入的同时保证两堆的大小之差不超过一，如果超过，则将数量多的堆弹出堆顶元素放到另一个堆中，确保他们两个堆顶就是数据中间的数 。
剑指 Offer 42. 连续子数组的最大和
class Solution {public:int maxSubArray(vector& nums) {int all = INT_MIN, temp = 0;for (int i = 0; i < nums.size(); i++) {temp += nums[i];all = max(all, temp);if (temp < 0) {temp = 0;}}return all;}};
这个类似于我之前写的包含min函数的栈，不过这里是使用一个变量一直存储最大值，另一个变量一直在顺着数组往后加，如果小于0了就将其归零继续加，直至数组末尾 。
剑指 Offer 43. 1～n 整数中 1 出现的次数
class Solution {public:int countDigitOne(int n) {int high = n / 10; //高位int cur = n % 10; //当前位int low = 0; //低位long int digit = 1; //位因子long int num = 0; //1个总个数while (high != 0 || cur != 0) {if (cur == 0) {num += high * digit;} else if (cur == 1) {num += high * digit + low + 1;} else {num += (high + 1) * digit;}//到一下位digit *= 10;cur = high % 10;high /= 10;low = n % digit;}return num;}};