力扣第 376 场周赛（三分，中位数贪心，滑动窗口）

 用一个哈希表记录一下，然后遍历统计一下即可。

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        int n = grid.size();
        unordered_set<int> st;
        vector<int> res;
        
        for(int i = 0; i < n; i ++ ) {
            for(int j = 0; j < n; j ++ ) {
                if(st.count(grid[i][j])) {
                    res.push_back(grid[i][j]);
                }
                st.insert(grid[i][j]);
            }
        }
        
        for(int i = 1; i <= n * n; i ++ ) {
            if(!st.count(i)) {
                res.push_back(i);
                break;
            }
        }
        
        return res;
    }
};

 排序+贪心

class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        vector<vector<int>> res;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        
        for(int i = 0; i + 2 < n; i += 3) {
            if(nums[i + 2] - nums[i] > k) return {};
        }
        
        for(int i = 0; i + 2 < n; i += 3) {
            res.push_back({nums[i], nums[i + 1], nums[i + 2]});
        }
        
        return res;
    }
};

 先是在比赛时想到的三分写法

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        def cost(x: int, flag: int) -> int:
            s = str(x)
            if flag == 0:
                y = int(s[:-1] + s[::-1])
            else:
                y = int(s + s[::-1])

            return sum(abs(k - y) for k in nums)


        def search(flag: int) -> int:
            l, r = 0, 99999
            while l + 2 < r:
                m1 = (l * 2 + r) // 3
                m2 = (l + r * 2) // 3
                f1 = cost(m1, flag)
                f2 = cost(m2, flag)
                if f1 > f2:
                    l = m1
                else:
                    r = m2

            return min(cost(l, flag), cost(r, flag), cost(l + 1, flag))


        return min(search(0), search(1))

然后是灵神讲的中位数贪心

pal = []
base = 1

while base <= 10000:
    for i in range(base, base * 10):
        x = i
        t = i // 10
        while t:
            x = x * 10 + t % 10
            t //= 10
        pal.append(x)
    if base <= 1000:
        for i in range(base, base * 10):
            x = t = i
            while t:
                x = x * 10 + t % 10
                t //= 10
            pal.append(x)
    base *= 10

pal.append(10**9 + 1)

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        nums.sort()
        
        def cost(i: int) -> int:
            target = pal[i]
            return sum(abs(x - target) for x in nums)

        n = len(nums)
        i = bisect_left(pal, nums[(n - 1) // 2])
        
        return min(cost(i - 1), cost(i))
        

 滑动窗口+前缀和操作统计+中位数贪心

class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        s = list(accumulate(nums, initial=0))

        def d_sum(l: int, i: int, r: int) -> int:
            left = nums[i] * (i - l) - (s[i] - s[l])
            right = s[r + 1] - s[i + 1] - nums[i] * (r - i)
            return left + right
        
        ans = left = 0
        for i in range(n):
            while d_sum(left, (left + i) // 2, i) > k:
                left += 1
            ans = max(ans, i - left + 1)

        return ans