写点什么

2024-07-27:用 go 语言,给定一个正整数数组,最开始可以对数组中的元素进行增加操作,每个元素最多加 1。 然后从修改后的数组中选出一个或多个元素,使得这些元素排序后是连续的。 要求找出最多可以选

  • 2024-07-27
    北京
  • 本文字数:859 字

    阅读完需:约 3 分钟

2024-07-27:用 go 语言,给定一个正整数数组,最开始可以对数组中的元素进行增加操作,每个元素最多加 1。


然后从修改后的数组中选出一个或多个元素,使得这些元素排序后是连续的。


要求找出最多可以选出的元素数量。


输入:nums = [2,1,5,1,1]。


输出:3。


解释:我们将下标 0 和 3 处的元素增加 1 ,得到结果数组 nums = [3,1,5,2,1] 。


我们选择元素 [3,1,5,2,1] 并将它们排序得到 [1,2,3] ,是连续元素。


最多可以得到 3 个连续元素。


答案 2024-07-27:


chatgpt


题目来自 leetcode3041。

大体步骤如下:

1.定义一个函数 maxSelectedElements(nums),参数为一个整数数组 nums,返回最多可选出的连续元素数量。


2.初始化一个空的映射 f 用于存储每个数字及其相邻数字出现的次数。


3.对输入的数组 nums 进行排序,确保数组中的元素是升序排列。


4.遍历排序后的数组 nums,对于数组中的每个元素 x:


  • 更新映射 f[x+1] 为 f[x] + 1,表示 x+1 与 x 相邻的数字出现的次数。

  • 更新映射 f[x] 为 f[x-1] + 1,表示 x 与 x-1 相邻的数字出现的次数。


5.遍历映射 f 中的所有值,取其中的最大值作为答案。


总的时间复杂度为 O(nlogn) 其中 n 是输入数组的长度,主要由排序算法造成。


总的额外空间复杂度为 O(n),用来存储映射 f。

Go 完整代码如下:

package main
import ( "fmt" "slices")
func maxSelectedElements(nums []int) (ans int) { slices.Sort(nums) f := map[int]int{} for _, x := range nums { f[x+1] = f[x] + 1 f[x] = f[x-1] + 1 } for _, res := range f { ans = max(ans, res) } return}

func main() { nums:=[]int{2,1,5,1,1} fmt.Println(maxSelectedElements(nums))}
复制代码


Python 完整代码如下:

# -*-coding:utf-8-*-
def maxSelectedElements(nums): nums.sort() f = {} ans = 0 for x in nums: f[x+1] = f.get(x, 0) + 1 f[x] = f.get(x-1, 0) + 1 for res in f.values(): ans = max(ans, res) return ans
nums = [2, 1, 5, 1, 1]print(maxSelectedElements(nums))
复制代码



发布于: 刚刚阅读数: 5
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2024-07-27:用go语言,给定一个正整数数组,最开始可以对数组中的元素进行增加操作,每个元素最多加1。 然后从修改后的数组中选出一个或多个元素,使得这些元素排序后是连续的。 要求找出最多可以选_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区