豆包MarsCode算法题:数组元素之和最小化

数组元素之和最小化

  • 问题描述
  • 思路分析
    • 分析
    • 思路
    • 解决方案
  • 参考代码(Python)
    • 代码分析
      • 1. `solution` 函数
      • 2. 计算 `1 + 2 + 3 + ... + n` 的和
      • 3. 乘以 `k` 得到最终的数组元素之和
      • 4. 主程序(`if __name__ == '__main__':`)
        • 代码的时间复杂度分析:
        • 代码的空间复杂度分析:

问题描述

在这里插入图片描述

思路分析

分析

  1. 元素两两不同:数组中所有元素必须是不同的。
  2. 元素的最大公约数为 k:所有的元素必须是 k 的倍数。
  3. 元素之和尽可能小:为了让元素的和最小,我们需要尽量选择最小的满足条件的元素。

思路

  • 首先,如果数组元素的最大公约数为 k,那么所有元素可以表示成 k * a1, k * a2, ..., k * an 的形式,其中 a1, a2, ..., ann 个互质的数。
  • 为了满足“元素之和尽可能小”,我们应该选择最小的 n 个互质数,且这些数的公约数为 1。
  • 最小的 n 个互质数依次是:1, 2, 3, …, n。

解决方案

  • 选择最小的 n 个互质数,分别是 1, 2, 3, ..., n
  • 这些数分别乘以 k,得到的数组为 k, 2k, 3k, ..., nk
  • 最终的数组元素之和就是 k * (1 + 2 + 3 + ... + n)

1 + 2 + 3 + ... + n 的和是一个已知公式:n * (n + 1) / 2

因此,数组的最小和就是 k * (n * (n + 1) / 2)

参考代码(Python)

def solution(n: int, k: int) -> int:# 计算 1 + 2 + 3 + ... + n 的和sum_of_first_n = n * (n + 1) // 2# 乘以 k 得到最终的和return k * sum_of_first_nif __name__ == '__main__':print(solution(n = 3, k = 1) == 6)  # 1+2+3 = 6print(solution(n = 2, k = 2) == 6)  # 2+4 = 6print(solution(n = 4, k = 3) == 30) # 3+6+9+12 = 30

代码分析

1. solution 函数

def solution(n: int, k: int) -> int:
  • 功能:该函数的作用是返回一个包含 n 个元素的数组,其满足题目的条件:数组中的元素两两不同,所有元素的最大公约数为 k,并且这些元素之和尽可能小。
  • 参数
    • n: 数组中元素的个数。
    • k: 数组中每个元素的最大公约数。

2. 计算 1 + 2 + 3 + ... + n 的和

sum_of_first_n = n * (n + 1) // 2
  • 解释:为了尽可能使数组元素之和最小,我们选择最小的 n 个互质数,这些数是 1, 2, 3, ..., n

  • 数学公式1 + 2 + 3 + ... + n 的和是一个经典的数学公式:
    在这里插入图片描述

    该公式计算的是从 1 到 n 的所有整数的和。这个公式的时间复杂度是 O(1),只需要常数时间即可计算出结果。

  • 具体实现:使用整数除法 // 来确保计算结果为整数(在 Python 中,/ 默认会返回浮动类型,而我们这里需要整数结果)。

3. 乘以 k 得到最终的数组元素之和

return k * sum_of_first_n
  • 解释:计算完 1 + 2 + 3 + ... + n 的和后,乘以 k 得到数组中所有元素的和。
    • 例如,数组中的元素是 k, 2k, 3k, ..., nk,这些元素的和就是 k * (1 + 2 + 3 + ... + n),即 k 乘以 sum_of_first_n
    • 由于我们已经在前一步计算了 sum_of_first_n,这一步是将它乘以 k 得到最终的结果。

4. 主程序(if __name__ == '__main__':

if __name__ == '__main__':print(solution(n = 3, k = 1) == 6)  # 1+2+3 = 6print(solution(n = 2, k = 2) == 6)  # 2+4 = 6print(solution(n = 4, k = 3) == 30) # 3+6+9+12 = 30
  • 这里的 if __name__ == '__main__': 用来检查该文件是否作为主程序执行。如果是,代码就会运行里面的测试代码;如果这个文件被作为模块导入,里面的测试代码就不会执行。
  • 测试
    • solution(n = 3, k = 1) 返回的是 6,因为选取的是 1, 2, 3,它们的和是 6
    • solution(n = 2, k = 2) 返回的是 6,选取的是 2, 4,它们的和是 6
    • solution(n = 4, k = 3) 返回的是 30,选取的是 3, 6, 9, 12,它们的和是 30
代码的时间复杂度分析:
  • 计算和 1 + 2 + 3 + ... + n:这部分使用了数学公式,时间复杂度是 O(1)。
  • 乘以 k:这只是一个常数乘法操作,时间复杂度也是 O(1)。
  • 总时间复杂度:由于这两个操作的时间复杂度都是 O(1),所以整体时间复杂度是 O(1)。
代码的空间复杂度分析:
  • 该函数只使用了常数空间(除了输入和输出),所以空间复杂度也是 O(1)。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

WebRTC视频 05 - 视频采集类 VideoCaptureDS 下篇

WebRTC视频 01 - 视频采集整体架构 WebRTC视频 02 - 视频采集类 VideoCaptureModule WebRTC视频 03 - 视频采集类 VideoCaptureDS 上篇 WebRTC视频 04 - 视频采集类 VideoCaptureDS 中篇 WebRTC视频 05 - 视频采集类 VideoCaptureDS 下篇(本文) 一、前言…

ffmpeg 最强大的视频工具

文章目录 一、ffmpeg安装二、基本用法1、文件格式转换2、视频过滤器 filter3、剪切4、合并5、音频过滤器6、删除轨道7、简单应用:录屏 一、ffmpeg安装 windows下可以上官网 https://www.ffmpeg.org/download.html下载: 下载好后,解压缩&…

初识算法 · 位运算(2)

目录 前言: 判定字符是否唯一 丢失的数字 比特位计数 只出现一次的数字III 前言: ​本文的主题是位运算,通过四道题目讲解,一道是判断字符是否唯一,一道是只出现一次的数字III,一道是比特位计数&…

大数据新视界 -- 大数据大厂之 Impala 性能优化:基于数据特征的存储格式选择(上)(19/30)

💖💖💖亲爱的朋友们,热烈欢迎你们来到 青云交的博客!能与你们在此邂逅,我满心欢喜,深感无比荣幸。在这个瞬息万变的时代,我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

[产品管理-76]:延续是创新与颠覆式创新的比较

目录 一、概述 1、定义与特征 2、市场影响与竞争策略 3、实施难度与风险 4、案例分析 二、示例 1. 延续性创新示例 2. 创新示例 3. 颠覆式创新示例 一、概述 延续性创新与颠覆式创新是技术创新领域的两种重要策略,它们在多个方面存在显著差异。 以下是对…

JAVA学习日记(十五) 数据结构

一、数据结构概述 数据结构是计算机底层存储、组织数据的方式。 数据结构是指数据相互之间以什么方式排列在一起的。 数据结构是为了更加方便的管理和使用数据,需要结合具体的业务场景来进行选择。 二、常见的数据结构 (一)栈 特点&…

自动化测试工具Ranorex Studio(三十)-代码模块中使用变量快照

为了在代码模块中使用数据连接器提供的值,你需要在代码中添加一个变量。使用右键菜单项’Insert Module Variable’。 添加一个新的变量到您的代码模块 指定变量名和默认值 通过添加一个新的变量,Ranorex Studio 会在光标位置插入一段新代码——由一个…

Python技巧:查询模块的版本号的方法

1,pycharm里面的 Python interpreter 或者 Python package 2,通过 __version_info__ import matplotlib print(matplotlib.__version_info__) 3,查看目录里面的 _version.py 文件

​​​​​​​15TS Series TVS 的解析

15TS Series 1500W Transient Voltage Suppresso指的是一系列高性能的瞬态电压抑制二极管(Transient Voltage Suppressor,TVS),这些二极管由时源芯微(TimeSource)设计用于保护敏感的电子设备免受瞬态过电压…

Python学习从0到1 day27 Python 高阶技巧 ① 闭包

目录 一、闭包 作用 示例 二、nonlocal关键字 示例 三、atm取钱的闭包实现 四、闭包注意事项 优点 缺点 我陪你走了一段路,你最了解我不是吗 —— 24.11.11 一、闭包 在函数嵌套的前提下,内部函数使用了外部函数的变量,并且外部函数返回了内部…

python成长技能之网络编程

文章目录 一、初识Socket1.1 什么是 Socket?1.2 socket的基本操作1.3 socket常用函数 二、基于UDP实现客户端与服务端通信三、基于TCP实现客户端与服务端通信四、使用requests模块发送http请求 一、初识Socket 1.1 什么是 Socket? Socket又称"套接字",…

[ACTF2020 新生赛]Upload 1--详细解析

信息收集 题目告诉我们是一道upload,也就是文件上传漏洞题目。 进入界面,是一个灯泡,将鼠标放在图标上就会出现文件上传的相应位置: 思路 文件上传漏洞,先看看有没有前端校验。 在js源码中找到了前端校验&#xff…

光伏设计软件怎么选?有哪些推荐?

在光伏电站的开发建设中,专业设计软件是提升电站能效、降低开发成本的重要工具。市场上存在许多优秀的光伏设计软件,能够通过还原现状和三维建模来呈现出最符合实际需求的设计方案,究竟该怎么选呢? -易用性:一些软件操…

刷题强训(day06) -- 大数加法、链表相加、大数乘法

目录 1、大数加法 1.1 题目 1.2 思路 1.3 代码实现 2、链表相加(二) 2.1 题目 2.2 思路 2.3 代码实现 3、大数乘法 3.1 题目 3.2 思路 3.3 代码实现 1、大数加法 1.1 题目 1.2 思路 这道题可以模拟列竖式相加解答, 将每一位都转…

雷池waf安装并部署防护站点

雷池waf安装并部署防护站点 最低配置要求 操作系统:Linux 指令架构:x86_64 软件依赖:Docker 20.10.14 版本以上 软件依赖:Docker Compose 2.0.0 版本以上 最小化环境:1 核 CPU / 1 GB 内存 / 5 GB 磁盘 写在前面 本文…

AI技术赋能电商行业:创新应用与未来展望

💓 博客主页:倔强的石头的CSDN主页 📝Gitee主页:倔强的石头的gitee主页 ⏩ 文章专栏:《热点时事》 期待您的关注 引言 随着科技的飞速发展,人工智能(AI)技术正逐步渗透到各行各业&a…

【Linux】进程(状态)

大家好呀,我是残念,希望在你看完之后,能对你有所帮助,有什么不足请指正!共同学习交流哦 本文由:残念ing原创CSDN首发,如需要转载请通知 个人主页:残念ing-CSDN博客,欢迎各…

自动化测试框架的搭建详解

🍅 点击文末小卡片 ,免费获取软件测试全套资料,资料在手,涨薪更快 最近好多小伙伴都在说接口自动化测试,那么究竟什么是接口自动化测试呢?让我们一起往下看就知道了,首先我们得先弄清楚下面这…

重拾CSS,前端样式精读-媒体查询

前言 本文收录于CSS系列文章中,欢迎阅读指正 说到媒体查询,大家首先想到的可能是有关响应式的知识点,除此之外,它还可以用于条件加载资源,字体大小,图像和视频的优化,用户界面调整等等方面&am…

4TS Series TVS 的解析

4TS Series 400W Transient Voltage Suppressor指的是时源芯微(TimeSource)生产的一系列瞬态电压抑制二极管(Transient Voltage Suppressor,TVS),这些二极管专门设计用于保护敏感电子设备免受雷电、电源浪涌…