14.中位数贪心

中位数贪心

定理：将数组 a 中的所有元素变为 a 的中位数是最优的。

如何理解？

假定所有的 nums[i] 均位于数轴上的 nums 的位置，要求我们在数轴上找出一个点 t，使得所有 nums[i] 到 t 的距离之和最小。

容易证明 t 不可能位于最小的 nums[0] 的左侧，也不可能位于最大的 nums[n-1] 的右侧，否则我们「至少」能够将目标点调整为 最小的 nums[0] 或 最大的 nums[n-1] 来得到更小的距离总和。

举例：

考虑变为 a[0] 和 a[n-1] 的中间位置 x ，a[0] 移动 b 步，a[n-1] 移动 c 步，总共 b+c 步，当变为 x+1 时，a[0] 移动 b+1 步，a[n-1] 移动 c-1 步，总共 b+c 步。

因此变为 a[0] 和 a[n-1] 中间节点时，a[0]+a[n-1] 总的步数是相同的。

当考虑变为 a[1] 和 a[n-2] 的中间位置 x 时，可以发现变成了和原问题更小的子问题。

疑问：怎么证明最终数字一定是矩阵中原有数字的时候操作最小呢？也就是最终变化得到的值不在原矩阵中的操作数是否更小？

  • 分奇偶讨论，如果是奇数个数就选中位数，如果是偶数个数就可以选中间两个数中的一个，或者这两个数中间的数也可以。只不过无论怎么取，只要是中位数或两个中位数之间的，算出来的操作数都是一样的最小值。

中位数贪心题单

  • 462. 最小操作次数使数组元素相等 II

  • 2033. 获取单值网格的最小操作数 1672

  • 2448. 使数组相等的最小开销 2005

  • 2607. 使子数组元素和相等 2071

  • 1703. 得到连续 K 个 1 的最少相邻交换次数 2467

参考：

https://leetcode.cn/problems/minimum-cost-to-make-array-equalindromic/solutions/2569308/yu-chu-li-hui-wen-shu-zhong-wei-shu-tan-7j0zy/

https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/solutions/1504154/by-ac_oier-db44/

462. 最小操作次数使数组元素相等 II

中等

给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最小操作数。

在一次操作中，你可以使数组中的一个元素加 1 或者减 1 。

示例 1：

输入：nums = [1,2,3]
输出：2
解释：
只需要两次操作（每次操作指南使一个元素加 1 或减 1）：
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

示例 2：

输入：nums = [1,10,2,9]
输出：16

提示：

  • n == nums.length
  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
class Solution {
    // 中位数贪心
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int cnt = 0, n = nums.length;
        int target = nums[n / 2];
        for(int i = 0; i < n; i++){
            cnt += Math.abs(nums[i] - target);
        }
        return cnt;
    }
}

2033. 获取单值网格的最小操作数

中等

给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x 。每一次操作，你可以对 grid 中的任一元素 加 x 或 减 x 。

单值网格 是全部元素都相等的网格。

返回使网格化为单值网格所需的 最小 操作数。如果不能，返回 -1 。

示例 1：

img

输入：grid = [[2,4],[6,8]], x = 2
输出：4
解释：可以执行下述操作使所有元素都等于 4 ： 
- 2 加 x 一次。
- 6 减 x 一次。
- 8 减 x 两次。
共计 4 次操作。

示例 2：

img

输入：grid = [[1,5],[2,3]], x = 1
输出：5
解释：可以使所有元素都等于 3 。

示例 3：

img

输入：grid = [[1,2],[3,4]], x = 2
输出：-1
解释：无法使所有元素相等。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • 1 <= x, grid[i][j] <= 104
class Solution {
    /**
    要使任意两元素最终相等，这两元素的差必须是 x 的倍数，否则无法通过加减 x 来相等
     */
    public int minOperations(int[][] grid, int x) {
        int m = grid.length, n = grid[0].length;
        int[] nums = new int[m*n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                nums[i*n + j] = grid[i][j];
            }
        } 
        Arrays.sort(nums);
        int target = nums[m*n / 2], res = 0;
        for(int i = 0; i < m*n; i++){
            int diff = Math.abs(nums[i] - target);
            if(diff % x != 0) return -1;
            res += diff / x;
        }
        return res;

    }
}

2448. 使数组相等的最小开销

困难

给你两个下标从 0 开始的数组 nums 和 cost ，分别包含 n 个 正 整数。

你可以执行下面操作 任意 次：

  • 将 nums 中 任意 元素增加或者减小 1 。

对第 i 个元素执行一次操作的开销是 cost[i] 。

请你返回使 nums 中所有元素 相等 的 最少 总开销。

示例 1：

输入：nums = [1,3,5,2], cost = [2,3,1,14]
输出：8
解释：我们可以执行以下操作使所有元素变为 2 ：
- 增加第 0 个元素 1 次，开销为 2 。
- 减小第 1 个元素 1 次，开销为 3 。
- 减小第 2 个元素 3 次，开销为 1 + 1 + 1 = 3 。
总开销为 2 + 3 + 3 = 8 。
这是最小开销。

示例 2：

输入：nums = [2,2,2,2,2], cost = [4,2,8,1,3]
输出：0
解释：数组中所有元素已经全部相等，不需要执行额外的操作。

提示：

  • n == nums.length == cost.length
  • 1 <= n <= 105
  • 1 <= nums[i], cost[i] <= 106
  • 测试用例确保输出不超过 253-1。

方法一：枚举 + 考虑变化量

class Solution {
    /** 方法一，枚举 + 考虑变化量
    首先计算所有元素等于nums[0]的总开销total和所有cost的和sumCost
    然后考虑要使所有元素都等于nums[1]，total的变化量是多少
    1. 有cost[0]这么多的开销要增加nums[1]-nums[0]
    2. 有sumCost - cost[0]这么多开销要减少 nums[1]-nums[0]
    因此total减少了 (sumCost - 2cost[0])*(nums[1] - nums[0])
     */
    public long minCost(int[] nums, int[] cost) {
        int n = nums.length;
        int[][] pairs = new int[n][2];
        for(int i = 0; i < n; i++){
            pairs[i][0] = nums[i];
            pairs[i][1] = cost[i];
        }
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        // 首先计算所有元素等于nums[0]的总开销total和所有cost的和sumCost
        long total = 0, sumCost = pairs[0][1];
        for(int i = 1; i < n; i++){
            total += (long)(pairs[i][0] - pairs[0][0]) * pairs[i][1];
            sumCost += pairs[i][1];
        }
        // long sumCost=Arrays.stream(cost).sum();
        long ans = total;
        for(int i = 1; i < n; i++){
            // 考虑从上一位nums[i-1]的total开销变为nums[i]，变化量是多少
            sumCost -= 2 * pairs[i-1][1];
            total -= (long)(sumCost) * (pairs[i][0] - pairs[i-1][0]);
            ans = Math.min(ans, total);
        }
        return ans;
    }
}

方法二：中位数贪心

class Solution {
    /**
    中位数贪心，把cost[i]理解成nums[i]的出现次数
    按照方法一排序，然后不断累加cost[i],首次累加到 >= sumCost/2 时就找到了中位数
     */
    public long minCost(int[] nums, int[] cost) {
        int n = nums.length;
        int[][] pairs = new int[n][2];
        for(int i = 0; i < n; i++){
            pairs[i][0] = nums[i];
            pairs[i][1] = cost[i];
        }
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        long s = 0, mid = 0;
        for(int i = 0; i < n; i++){
            mid += pairs[i][1];
        }
        // 由于 sumCost 可能是奇数，所以要上取整
        mid = (mid + 1) / 2;
        for(int i = 0; i < n; i++){
            s += pairs[i][1];
            if(s >= mid){
                int x = pairs[i][0];
                // 把所有数变成 x
                long res = 0;
                for(int j = 0; j < n; j++){
                    res += (long)(Math.abs(pairs[j][0]- x)) * pairs[j][1];
                }
                return res;
            }
        }
        return -1;
    }
}

2607. 使子数组元素和相等

中等

给你一个下标从 0 开始的整数数组 arr 和一个整数 k 。数组 arr 是一个循环数组。换句话说，数组中的最后一个元素的下一个元素是数组中的第一个元素，数组中第一个元素的前一个元素是数组中的最后一个元素。

你可以执行下述运算任意次：

  • 选中 arr 中任意一个元素，并使其值加上 1 或减去 1 。

执行运算使每个长度为 k 的 子数组 的元素总和都相等，返回所需要的最少运算次数。

子数组 是数组的一个连续部分。

示例 1：

输入：arr = [1,4,1,3], k = 2
输出：1
解释：在下标为 1 的元素那里执行一次运算，使其等于 3 。
执行运算后，数组变为 [1,3,1,3] 。
- 0 处起始的子数组为 [1, 3] ，元素总和为 4 
- 1 处起始的子数组为 [3, 1] ，元素总和为 4 
- 2 处起始的子数组为 [1, 3] ，元素总和为 4 
- 3 处起始的子数组为 [3, 1] ，元素总和为 4

示例 2：

输入：arr = [2,5,5,7], k = 3
输出：5
解释：在下标为 0 的元素那里执行三次运算，使其等于 5 。在下标为 3 的元素那里执行两次运算，使其等于 5 。
执行运算后，数组变为 [5,5,5,5] 。
- 0 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 1 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 2 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 3 处起始的子数组为 [5, 5, 5] ，元素总和为 15

提示：

  • 1 <= k <= arr.length <= 105
  • 1 <= arr[i] <= 109

中位数贪心 + 裴蜀定理

class Solution {
    // a[i] + a[i+1] + .. + a[i+k-1]
    // = a[i+1] + a[i+2] + .. + a[i+k]
    // ==> a[i] = a[i+k]

    // 按照i mod k 的结果将 arr 分组，对每一组（记为b）：
    // 让数组b的所有元素相等的最少运算次数：
    // 根据中位数贪心：将数组b的所有元素变为b的中位数是最优的
    // 裴蜀定理 ： 一个循环数组如果既有周期n，又有周期k，则必然有周期gcd(n,k)
    public long makeSubKSumEqual(int[] arr, int k) {
        int n = arr.length;
        k = gcd(k, n);
        long ans = 0;
        for(int i = 0; i < k; i++){
            List<Integer> list = new ArrayList<>();
            for(int j = i; j < n; j += k){
                list.add(arr[j]);
            }
            Collections.sort(list);
            int mid = list.get(list.size() / 2);
            for(int x : list){
                ans += Math.abs(x - mid);
            }
        }
        return ans;
    }

    public int gcd(int x, int y){
        return y == 0 ? x : gcd(y, x%y);
    }
}

1703. 得到连续 K 个 1 的最少相邻交换次数

困难

给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。每一次移动，你可以选择 相邻 两个数字并将它们交换。

请你返回使 nums 中包含 k 个 连续 1 的 最少 交换次数。

示例 1：

输入：nums = [1,0,0,1,0,1], k = 2
输出：1
解释：在第一次操作时，nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1 。

示例 2：

输入：nums = [1,0,0,0,0,0,1,1], k = 3
输出：5
解释：通过 5 次操作，最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1] 。

示例 3：

输入：nums = [1,1,0,1], k = 2
输出：0
解释：nums 已经有连续 2 个 1 了。

提示：

  • 1 <= nums.length <= 105
  • nums[i] 要么是 0 ，要么是 1 。
  • 1 <= k <= sum(nums)

https://leetcode.cn/problems/minimum-adjacent-swaps-for-k-consecutive-ones/solutions/2024387/tu-jie-zhuan-huan-cheng-zhong-wei-shu-ta-iz4v/

class Solution {
    public int minMoves(int[] nums, int k) {
        int n = nums.length;
        int[] pos = new int[n];
        int index = 0;
        // 例如：[1,0,0,1,0,1,1,1,0,1,1] => [0,3,5,6,7,9,10]
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                pos[index++] = i;
            }
        }
        int ans = 0, count = 0, mid = k / 2;
        // 定长滑窗模板: 
        // 1.计算第一个长度为k的窗口, k = 5, pos[i] - pos[i - 1] - 1表示相邻1之间0的个数 
        // [0,3,5,6,7] => (3-0-1)*1 + (5-3-1)*2 + (6-5-1)*2 + (7-6-1)*1 = 4
        for (int i = 1; i < k; i++) {
            count += (pos[i] - pos[i - 1] - 1) * Math.min(i, k - i);
        }
        ans = count;
        // 2.窗口按步长滑动 [0,3,5,6,7] => [3,5,6,7,9]
        // [0,3,5,6,7] => (3-0-1)*1 + (5-3-1)*2 + (6-5-1)*2 + (7-6-1)*1 = 4
        // [3,5,6,7,9] =>             (5-3-1)*1 + (6-5-1)*2 + (7-6-1)*2 + (9-7-1)*1 = 2
        // 通过对比发现：count -= (3-0-1)*1 + (5-3-1)*1 + (6-5-1)*0 = 3 - 0 + 5 - 3 + 1 + 1= 5 - 0 + 2
        //             count += (7-6-1)*1 + (9-7-1)*1 = 7 - 6 + 9 - 7 - 1 - 1 = 9 - 6 - 2
        // 类似于差分和前缀和的关系，加减2相互抵消，所以最后结果与窗口内两端点和中位数有关
        for (int i = k; i < index; i++) {
            count -= pos[i - k + mid] - pos[i - k]; // 上个区间中位数下标 - 上个区间左端点
            count += pos[i] - pos[i - mid]; // 当前区间右端点 - 当前区间中位数
            ans = Math.min(ans, count);
        }
        return ans;
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/260866.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【昆明*线上同步】最新ChatGPT/GPT4科研实践应用与AI绘图技术及论文高效写作

【昆明*线上同步】最新ChatGPT/GPT4科研实践应用与AI绘图技术及论文高效写作

详情点击查看福利&#xff1a;【昆明*线上同步】最新ChatGPT/GPT4科研实践应用与AI绘图技术及论文高效写作 目标&#xff1a; 1、熟练掌握ChatGPT提示词技巧及各种应用方法&#xff0c;并成为工作中的助手。 2、通过案例掌握ChatGPT撰写、修改论文及工作报告&#xff0c;提供…
阅读更多...
Actuator内存泄露及利用Swagger未授权自动化测试实现

Actuator内存泄露及利用Swagger未授权自动化测试实现

目录 0x00 前言 0x01 Actuator 泄露及利用 1、Actuator heapdump 内存泄露 2、知道泄露后如何进一步利用 3、如何发现 Actuator 泄露&#xff08;白盒/黑盒&#xff09; 0x02 Swagger自动化测试 1、什么是Swagger&#xff1f; 2、PostmanBurpSuiteXray 联动 3、思考 0x…
阅读更多...
XC8284B 高效率12MHz,34V升压LED驱动器 LED背光驱动、闪光灯

XC8284B 高效率12MHz,34V升压LED驱动器 LED背光驱动、闪光灯

XC8284B是一个升压转换器驱动多达9个系列白色LED的单节离子电池设计的。其300mV反馈电压降低功率损耗&#xff0c;提高效率。优化后的工作频率可以满足LC滤波器小值和低工作电流的要求&#xff0c;具有较高的效率。内置软启动功能&#xff0c;可减少浪涌电流。微型封装类型为节…
阅读更多...
TensorRT 简单介绍

TensorRT 简单介绍

一、TensorRT 对于算法工程师来说&#xff0c;相信大家已经对TensorRT耳熟能详了&#xff0c;那么这个TensorRT是什么呢&#xff1f; 其实&#xff0c;TensorRT是一个可以在NVIDIA各种GPU硬件平台下运行的推理引擎&#xff0c;同时也是一个高性能的深度学习推理优化器&#x…
阅读更多...
在ClickHouse数据库中启用预测功能

在ClickHouse数据库中启用预测功能

在这篇博文中&#xff0c;我们将介绍如何将机器学习支持的预测功能与 ClickHouse 数据库集成。ClickHouse 是一个快速、开源、面向列的 SQL 数据库&#xff0c;对于数据分析和实时分析非常有用。该项目由 ClickHouse&#xff0c; Inc. 维护和支持。我们将探索它在需要数据准备以…
阅读更多...
SDK和API的区别

SDK和API的区别

简单一句话&#xff1a;api就是一个函数接口&#xff0c;函数内容的功能无法独立运行&#xff0c;只有连接到服务器才可以发挥作用。 sdk是开发工具包&#xff0c;含有功能和函数接口&#xff0c;可以独立运行。 废话篇&#xff1a; 内容不同&#xff1a;SDK为API 提供能量源。…
阅读更多...
【扩散模型】8、DALL-E2 | 借助 CLIP 的图文对齐能力来实现文本到图像的生成

【扩散模型】8、DALL-E2 | 借助 CLIP 的图文对齐能力来实现文本到图像的生成

文章目录 一、背景二、方法2.1 Decoder2.2 Prior 三、图像控制3.1 Variations3.2 Interpolations3.3 Text Diffs 四、探索 CLIP 的潜在空间五、文本到图像的生成5.1 先验的重要性5.2 人类评价5.3 多样性和保真性的平衡5.3 在 COCO 上对比 论文&#xff1a;DALLE.2 代码&#x…
阅读更多...
Redis 中的 RDB 和 AOF 持久化机制

Redis 中的 RDB 和 AOF 持久化机制

一、Redis 持久化简介 Redis 的持久化功能是区别于 Memcached 显著特性&#xff0c;数据持久化可以保证系统在发生宕机和重启后数据不会丢失&#xff0c;对于 redis 这种存储在内存中的数据库显得尤为重要。 在 Redis 4.0 以前数据持久化的方式主要有两种 RDB&#xff08;Redi…
阅读更多...
初学gitrepo的种种

初学gitrepo的种种

经过各种折腾之后&#xff0c;发现git其实还是很简单的&#xff1b; 首先你需要两台机器&#xff0c;一台作为服务器&#xff0c;一台作为开发机器&#xff0c;开发机器从服务器上拉取代码。 目 目录 git建仓 开发机器拉取代码 初始化仓代码 repo管理 repo工具的下载 …
阅读更多...
Ansible的脚本---Playbook剧本编写

Ansible的脚本---Playbook剧本编写

playbook的组成部分 1、 tasks&#xff1a;任务 在目标主机上需要执行的操作。使用模块定义这些操作。每个任务都是一个模块的调用。 2、 variables&#xff1a;变量 用于存储和传递数据。类似于shell脚本中的变量。变量可以自定义。可以在playbook当中定义为全局变量&…
阅读更多...
Go 语言实战：掌握正则表达式的应用与技巧

Go 语言实战：掌握正则表达式的应用与技巧

Go 语言实战&#xff1a;掌握正则表达式的应用与技巧 1. 引言2. 正则表达式基础2.1 基本概念2.2 常见元素2.3 基本示例 3. Go语言中的正则表达式库3.1 引入regexp包3.2 编译正则表达式3.3 使用正则表达式3.4 示例代码 4. 常用正则表达式函数及使用示例4.1 MatchString4.2 FindS…
阅读更多...
配置自定义RedisTemplate 解决redis序列化java8 LocalDateTime

配置自定义RedisTemplate 解决redis序列化java8 LocalDateTime

目录 配置自定义RedisTemplate 引入依赖 配置连接redis 编写测试类 出现问题 配置序列化 解决redis序列化java8 LocalDateTime 问题背景 问题描述 问题分析 解决方案一&#xff08;全局&#xff09; 解决方案二&#xff08;单个字段&#xff09; 配置自定义RedisTe…
阅读更多...
在GitHub找开源项目

在GitHub找开源项目

在 GitHub 的搜索框里&#xff1a; 使用搜索关键词可以在 GitHub 上快速的找你需要的开源项目&#xff1a; 限制搜索范围 通过 in 关键词 (大小写不敏感) 限制搜索范围&#xff1a; 公式搜索范围in:name xxx项目名包含xxxin:description xxx项目描述包含xxxin:readme xxx项目…
阅读更多...
thymeleaf的个人总结

thymeleaf的个人总结

thymeleaf的java代码的用法 <!-- 静态页面模版引擎的依赖 --> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-thymeleaf</artifactId> </dependency> 我们在这里要配置一个具体的模版…
阅读更多...
CVE-2023-37582 Apache RocketMQ NameServer远程代码执行漏洞

CVE-2023-37582 Apache RocketMQ NameServer远程代码执行漏洞

上集回顾 CVE-2023-33246 RocketMQ RCE漏洞 影响版本 Apache RocketMQ NameServer 5.0.0 &#xff5e; 5.1.1 Apache RocketMQ NameServer 4.0.0 &#xff5e; 4.9.6 参考 https://xz.aliyun.com/t/12691 环境搭建 拉取镜像 docker pull apache/rocketmq:4.9.6 docker …
阅读更多...
Bugku- misc-插画-WP

Bugku- misc-插画-WP

下载得到一个zip&#xff0c;用WinRAR打开时发现有注释 注释&#xff1a; RnJlZV9GaWxlX0NhbW91ZmxhZ2UsIOmimOebruWlveWDjaYraMuumHjeimgeeahOagtWtkC4u 明显是base64&#xff0c;解码得到&#xff1a;Free_File_Camouflage, 题目好像是挺重要的样子… 百度发现这是一款隐写…
阅读更多...
微电网优化(Matlab复现)— 微电网两阶段鲁棒优化经济调度方法_刘一欣

微电网优化(Matlab复现)— 微电网两阶段鲁棒优化经济调度方法_刘一欣

论文链接&#xff1a;微电网两阶段鲁棒优化经济调度方法 - 中国知网 代码链接&#xff1a;https://m.tb.cn/h.5Mg7fCo?tkhnpmWgZiv2R 复现效果&#xff1a; 运行环境&#xff1a;Matlab 2020bCplexyalmip 1 微电网结构 图 1 所示为典型的微电网结构&#xff0c;由可控分布式…
阅读更多...
uniapp实现豆瓣电影微信小程序（附源码）

uniapp实现豆瓣电影微信小程序（附源码）

演示 运行 基于本地代理1 npm run dev:proxy1基于本地代理2 npm run dev:proxy2基于nginx 代理 npm run dev:nginx目录结构 |__ douban # 本地代理|__ app.js # 方式 1|__ proxy.js …
阅读更多...
基于vue-cli快速发布vue npm 包

基于vue-cli快速发布vue npm 包

一、编写组件 1. 初始化项目并运行 vue create vue-digital-countnpm run serve2. 组件封装 新建package文件夹 ​ 因为我们可能会封装多个组件&#xff0c;所以在src下面新建一个package文件夹用来存放所有需要上传的组件。 ​ 当然&#xff0c;如果只有一个组件&#xff…
阅读更多...
SQL面试题挑战01：打折日期交叉问题

SQL面试题挑战01：打折日期交叉问题

目录 问题&#xff1a;SQL解答&#xff1a;第一种方式&#xff1a;第二种方式&#xff1a; 问题&#xff1a; 如下为某平台的商品促销数据&#xff0c;字段含义分别为品牌名称、打折开始日期、打折结束日期&#xff0c;现在要计算每个品牌的打折销售天数&#xff08;注意其中的…
阅读更多...
最新文章

Copyright @ 2022~2023