查找给定数组的 GCD 对

酷瑶君_7920

酷瑶君_7920

2024-02-22

1483人浏览

转载

java问答:查找给定数组的gcd对是一个常见问题,需要对数组中的数字进行最大公约数(gcd)的计算。在java中,可以使用欧几里得算法来解决这个问题。在本篇文章中,php小编西瓜将介绍如何使用java编写一个方法来查找给定数组的gcd对,帮助读者更好地理解和应用这一算法。

问题内容

给定一个大小为 n 的整数数组,其中 n 是偶数。从数组中选取 2 个数字并找到 gcd。同样,从数组中剩余的项中选取 2 项并找到 gcd。重复上述步骤找到 gcd 对。对 gcd 值求和并得到最高的总和。

约束:

n is in range 2 to 20
arr[i] is in range 1 to 10^9

示例 1:

arr = [3,4,9,5]

答案:

4

说明:

a) gcd of (4,5) is 1
b) gcd of (3,9) is 3
sum = 1+3 = 4. this is the highest possible gcd sum.

示例 2:

arr = [1,2,3,4,5,6]

答案:

6

说明:

a) gcd of (1,5) is 1
b) gcd of (2,4) is 2
c) gcd of (3,6) is 3
sum = 1+2+3 = 6. this is the highest possible gcd sum.

这是我的代码:

jQuery+CSS3 3D立体图片排列布局代码
jQuery+CSS3 3D立体图片排列布局代码

jQuery+CSS3 3D立体图片排列布局代码

下载
public static int solve(int[] ar) {
   int n = ar.length;
   Arrays.sort(ar);
   int sum = 0;
   for(int i=0; i<n i int a="ar.get(i)," b="ar.get(n-i-1);" c="gcd(a,b);" sum return static gcd if is the call method recursively by replacing with and modulus as long else><p>我的代码适用于第一个示例,但为第二个示例提供了错误的输出。
我调试了一下,发现我使用的方法不正确。解决这个问题的正确方法是什么?</p>
<h2 class="daan">解决方法</h2>
<p>我们可以递归搜索所有可能的方法来计算总 gcd。怎么办?</p>
<p>如果数组只包含两个元素,我们可以只返回这两个元素的 gcd。</p>
<p>如果它包含更多,让我们迭代所有值对。对于每一对,我们计算它的 gcd,并且我们还使用删除了两个值的数组副本递归调用我们的函数。如果我们将两个计算的结果相加,我们就会得到当前选择的值对的总 gcd。</p>
<p>现在我们只跟踪迄今为止找到的最佳 gcd,并在最后返回它。</p>
<p>这是(应该)完全做到这一点的代码。</p>
<pre class="brush:java;toolbar:false;">int solve(int[] ar) {
  // if we have only two elements, there's not much else we can do.
  if(ar.length == 2) {
    return gcd(ar[0], ar[1]);
  }

  //keep track of the largest gcd
  int best = 0;
  
  // for every pair of values in the array
  //  make a copy of the array without the pair and call recursively
  for(int i = 0; i  best) // we found a better pair
        best = score;
    }
  }
  
  return best;
}

这个算法相当慢。如果您需要加快速度,至少有两个方面可以改进:

  • 计算 gcd 是一项昂贵的操作。 预先计算所有可能的唯一值对的 gcd 并将它们存储在哈希图中将消除双重计算。
  • 它会多次检查一些可能的排列。 (例如,在下一次递归中选择第一对,然后选择第二对与选择第二对,然后选择第一对相同)我对如何解决这个问题有一些模糊的想法,但今天晚上太晚了,抱歉。

很可能存在更快的算法,这只是我的想法。

编辑:好吧,经过一番睡眠后,我突然明白了。如果我们在创建对时省略外循环,我们将不会得到任何重复的对排序。基本上只是在各处用 0 替换 i ,如下所示:

for(int j = 1; j 

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

最大公约数 排列

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7436

4

Navicat创建数据库教程
Navicat创建数据库教程

本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

2026.11.20

0

7

Navicat入门教程大全
Navicat入门教程大全

本专题整理Navicat入门教程,从认识软件界面到开展数据库操作,介绍初次使用需要了解的知识和方法。内容兼顾连接配置、数据管理及日常使用中的疑问,方便用户按学习进度查阅,为后续实践和独立操作打好基础。

2026.11.20

0

17

Navicat数据库连接配置指南
Navicat数据库连接配置指南

从确认数据库信息到建立可用连接,本专题串联Navicat连接数据库的相关知识和操作方法。既有初次配置时需要了解的基础内容,也有连接后的检查思路,方便用户按实际需求查阅教程,逐步熟悉数据库连接的设置流程。

2026.11.20

0

10

PHP8.6数组与数据处理教程
PHP8.6数组与数据处理教程

本专题汇总PHP8.6数组与数据处理教程,涵盖CSV读取和导出、引用遍历删除、array_filter回调模式、配置键名冲突、pathinfo文件名校验、GMP大整数进制转换及UTF-8正则筛选,说明升级兼容变化、输入范围和失败处理方法。

2026.11.20

0

8

PHP8.6升级迁移教程
PHP8.6升级迁移教程

本专题汇总PHP8.6升级迁移与弃用接口改造教程,涵盖反射调用、对象属性赋值、标识符更名、构造函数与__debugInfo调整,以及插件类名检查、常量导出、ArrayIterator排序、SPL和DTO查询参数转换,帮助梳理弃用提示并完成代码兼容改造。

2026.11.20

0

10

PHP8.6安装配置与FPM运维教程
PHP8.6安装配置与FPM运维教程

本专题汇总PHP8.6正式版安装部署与FPM运维教程,涵盖Linux并存安装、独立ini配置、扩展重新编译、Nginx切换与回滚、FPM状态监控和慢日志排查,以及环境变量、请求超时、OPcache刷新和预加载配置。

2026.11.20

0

10

Nginx CVE-2026-123007排查与防护指南
Nginx CVE-2026-123007排查与防护指南

Nginx HTTP/2漏洞该怎么修复?本专题围绕CVE-2026-123007,介绍安全版本升级、模块兼容检查和配置恢复方法,以及日志排查、权限设置等后续加固操作,方便你按实际部署情况查找对应教程。

2026.11.20

20

8

GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

60

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.7万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 134.3万人学习