当前位置: 首页 > news >正文

dede网站打开慢广州各区进一步强化

dede网站打开慢,广州各区进一步强化,自己做软件 做网站需要学会哪些,重庆观音桥旅游攻略LeetCode 2966. 将数组分成差值不超过 k 的长度为 3 的子数组 原题链接:LeetCode CN - Divide Array Into Arrays With Max Difference 题目描述 给你一个整数数组 nums 和一个正整数 k。 你需要将这个数组划分为 n / 3 个长度为 3 的子数组。每个子数组必须满足&…

LeetCode 2966. 将数组分成差值不超过 k 的长度为 3 的子数组

原题链接:LeetCode CN - Divide Array Into Arrays With Max Difference


题目描述

给你一个整数数组 nums 和一个正整数 k

你需要将这个数组划分为 n / 3 个长度为 3 的子数组。每个子数组必须满足:

  • 子数组中任意两个元素之间的差值(绝对值)都 小于等于 k

要求返回这些子数组的列表(二维数组形式)。
如果无法划分满足条件的子数组,返回空数组 []
若有多个解,返回任意一个即可。


示例分析

示例 1:

输入:nums = [1,3,4,8,7,9], k = 3
输出:[[1,3,4],[7,8,9]]解释:
排序后:[1,3,4,7,8,9]
分组:
- [1,3,4] 差值最大为 3 
- [7,8,9] 差值最大为 2 

示例 2

输入:nums = [1,3,4], k = 1
输出:[]
解释:1 和 3 差为 2,超过了 1

思路解析

本质分析:

我们需要把数组分成若干组,每组正好 3 个元素,且这 3 个元素两两差值都 <= k

解法:排序 + 贪心分组

步骤:
  1. 判断 nums.size() % 3 != 0,无法整除,直接返回 []

  2. 对数组进行排序

  3. 每隔 3 个数组成一个子数组 [a,b,c],只需检查:

    • c - a <= k
    • 因为排序后,a <= b <= c,最大差值在 a 和 c 之间
  4. 若所有子数组都满足条件,返回所有子数组

  5. 若任意一组不满足,返回 []

为什么只需判断 max - min <= k

因为排序后:

  • 差值最大的一对是 最小值最大值
  • max - min <= k,则中间那个值也自然合法

代码实现

C++ 实现

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

Go 实现

import "sort"func divideArray(nums []int, k int) [][]int {n := len(nums)if n%3 != 0 {return [][]int{}}sort.Ints(nums)var res [][]intfor i := 0; i < n; i += 3 {if nums[i+2]-nums[i] > k {return [][]int{}}group := []int{nums[i], nums[i+1], nums[i+2]}res = append(res, group)}return res
}

边界测试用例

输入k输出说明
[1,2,3], 11[]3-1=2 > 1
[1,2,3], 22[[1,2,3]]合法
[10,13,11,7,8,9], 33[[7,8,9],[10,11,13]]合法
[1,2,3,4], 22[]不能整除

复杂度分析

  • 时间复杂度

    • 排序:O(n log n)
    • 分组判断:O(n)
    • 总体:O(n log n)
  • 空间复杂度

    • 排序:O(1)(就地排序)
    • 结果数组:O(n)

拓展思考

1. 如果要求每个子数组 长度为任意值,但差值仍需小于等于 k

  • 就不能使用固定步长分组了
  • 可考虑 双指针 + 滑动窗口

2. 如果允许的组数不确定,但要最多分组?

  • 可以用贪心策略 + union set 找最大匹配组

总结

  • 这是一个 排序 + 分段验证 的贪心题

  • 关键在于观察:

    • 只需判断一组的最大值和最小值差是否超过 k
  • 若不要求固定长度为 3,就需考虑滑动窗口等策略

http://www.dinnco.com/news/16403.html

相关文章:

  • 大兴网站开发网站建设价格什么软件可以发帖子做推广
  • 怎么自己做网站地图最好最全的搜索引擎
  • 青岛建网站需要花多少钱现在阳性最新情况
  • 如何在年报网站上做遗失公告线上营销推广
  • 目前做批发比较好的b2b网站免费网站建设seo
  • 电影大型网站制作互联网广告销售
  • 昆明做网站建设企业推荐深圳最新政策消息
  • 2018做网站前景如何网站网址查询工具
  • 绵阳城乡住房建设厅网站关键词检索怎么弄
  • 为什么打不开中国建设银行网站网站网上推广
  • 平台网站建设意见征求表全国疫情高峰感染高峰进度查询
  • 网站建设优化服务友情链接互换网站
  • 网站文章更新注意什么意思品牌运营
  • 如何备份一个网站网站seo策划方案实例
  • wordpress 信息网站今日重要新闻
  • 浙江建设部网站网站建设方案推广
  • 做带会员后台的网站用什么软件外链是什么
  • 电子购物网站建设视频网站媒体推广方案
  • 海南网站建设方案seo辅助优化工具
  • 做兼职在什么网站找比较好保定网站建设方案优化
  • 织梦儿童早教教育培训网站模板广州网络推广哪家好
  • 网站建设需要哪些素材中国 日本 韩国
  • 大连网站快速排名提升网站站外优化推广方式
  • vue.js合作做网站么seo培训课程
  • 做属于公司的网站有什么好处百度app手机版
  • 望牛墩镇仿做网站拼多多关键词优化步骤
  • 中国移动的网站模板网站查找工具
  • 花店网站建设个人小结首页关键词排名代发
  • 民权做网站免费建站免费推广的网站
  • 广州天河区做网站的公司怎么把网站排名到百度前三名