寒假刷题Day16

一、1471. 数组中的 k 个最强值

class Solution {
public:
    vector<int> getStrongest(vector<int>& arr, int k) {
        int n = arr.size();
        if (k >= n) {
            return arr; // 如果 k 大于等于数组长度，直接返回整个数组
        }

        // 先对数组进行排序
        sort(arr.begin(), arr.end());

        // 计算中位数
        int mid = arr[(n - 1) / 2];

        // 双指针法选择最强的 k 个元素
        int left = 0, right = n - 1;
        vector<int> ans;
        while (k > 0) {
            if (abs(arr[left] - mid) > abs(arr[right] - mid)) {
                ans.push_back(arr[left]);
                ++left;
            } else {
                ans.push_back(arr[right]);
                --right;
            }
            --k;
        }

        return ans;
    }
};

第一次用（k > 0）作while循环条件，这种思想可以定量取出需要的数字

二、LCR 159. 库存管理 III

简单？如简！虽然可以直接sort ，但是面试哒咩

1.堆排序O(nlogcnt)

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        vector<int> vec(cnt, 0);
        if (cnt == 0) { // 排除 0 的情况
            return vec;
        }
        priority_queue<int> Q;
        for (int i = 0; i < cnt; ++i) {
            Q.push(stock[i]);
        }
        for (int i = cnt; i < (int)stock.size(); ++i) {
            if (Q.top() > stock[i]) {
                Q.pop();
                Q.push(stock[i]);
            }
        }
        for (int i = 0; i < cnt; ++i) {
            vec[i] = Q.top();
            Q.pop();
        }
        return vec;
    }
};

用一个大根堆实时维护数组的前 cnt 小值。

由于 C++ 语言中的堆（即优先队列）为大根堆，我们可以这么做。而 Python 语言中的堆为小根堆，因此我们要对数组中所有的数取其相反数，才能使用小根堆维护前 cnt 小值。

2.快速选择——快排变种O(n) 

快排的划分函数每次执行完后都能将数组分成两个部分，小于等于分界值 pivot 的元素的都会被放到数组的左边，大于的都会被放到数组的右边，然后返回分界值的下标。与快速排序不同的是，快速排序会根据分界值的下标递归处理划分的两侧，而这里我们只处理划分的一边。
分区->递归排序->提取结果

class Solution {
    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[r]);
        return i + 1;
    }

    // 基于随机的划分
    int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l;
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }

    void randomized_selected(vector<int>& stock, int l, int r, int cnt) {
        if (l >= r) {
            return;
        }
        int pos = randomized_partition(stock, l, r);
        int num = pos - l + 1;
        if (cnt == num) {
            return;
        } else if (cnt < num) {
            randomized_selected(stock, l, pos - 1, cnt);
        } else {
            randomized_selected(stock, pos + 1, r, cnt - num);
        }
    }

public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand((unsigned)time(NULL));
        randomized_selected(stock, 0, (int)stock.size() - 1, cnt);
        vector<int> vec;
        for (int i = 0; i < cnt; ++i) {
            vec.push_back(stock[i]);
        }
        return vec;
    }
};

三、633. 平方数之和

class Solution {
public:
    bool judgeSquareSum(int c) {
        int a = 0, b = sqrt(c);
        while(a <= b){
            if(a * a  > c - b * b){
                b--;
            }
            else if(a * a < c - b * b){
                a++;
            }
            else if(a * a  == c - b * b){
                return true;
            }
        }
        return false;
    }
};

1.b = sqrt(c) 剪枝

2.if判断语句这样写是为了防止溢出