-
被一道JAVA算法题难住了,请各位帮忙看下。0
数组 C[I] = A[I] + B[I] / 1,000,000.
例如 A 和 B:
A[0] = 0 B[0] = 500,000
A[1] = 1 B[1] = 500,000
A[2] = 2 B[2] = 0
A[3] = 2 B[3] = 0
A[4] = 3 B[4] = 0
A[5] = 5 B[5] = 20,000
则 C:
C[0] = 0.5
C[1] = 1.5
C[2] = 2.0
C[3] = 2.0
C[4] = 3.0
C[5] = 5.02
寻找一对下标(P, Q) 满足 0 ≤ P < Q < N 且 C[P] * C[Q] ≥ C[P] + C[Q].
上面的数组中满足条件的有:
(1, 4), 1.5 * 3.0 = 4.5 ≥ 4.5 = 1.5 + 3.0,
(1, 5), 1.5 * 5.02 = 7.53 ≥ 6.52 = 1.5 + 5.02,
(2, 3), 2.0 * 2.0 = 4.0 ≥ 4.0 = 2.0 + 2.0,
(2, 4) and (3, 4), 2.0 * 3.0 = 6.0 ≥ 5.0 = 2.0 + 3.0.
(2, 5) and (3, 5), 2.0 * 5.02 = 10.04 ≥ 7.02 = 2.0 + 5.02.
(4, 5), 3.0 * 5.02 = 15.06 ≥ 8.02 = 3.0 + 5.02.
现要求写个方法:
class Solution { public int solution(int[] A, int[] B); }
给出数组 A and B, 分别包含N个非负整数, 返回满足条件的下标对个数.
如果满足条件的下标对超过 1,000,000,000, 则返回 1,000,000,000.
例如,给出:
A[0] = 0 B[0] = 500,000
A[1] = 1 B[1] = 500,000
A[2] = 2 B[2] = 0
A[3] = 2 B[3] = 0
A[4] = 3 B[4] = 0
A[5] = 5 B[5] = 20,000
此方法应返回 8.
假设:
N 是整数,取值范围 [0..100,000];
数组A中的元素取值范围 [0..1,000];
数组B中的元素取值范围 [0..999,999];
数组C中的元素为非递减.
复杂度要求:
最坏的情况下,时间复杂度 O(N);
最坏的情况下,空间复杂度 O(1), 不包括参数的存储空间.2014年8月04日 06:28
2个答案 按时间排序 按投票排序
-
采纳的答案
分析如下:
从a*b>=a+b可以推到出:a*b>=4或者a*b=0同时必须满足a>1&b>1,这个可以通过数学方法得到.
由于a, b都是大于0的,所以我们可以依据以上规则对如上题目做这样一个优化:求一个数组(P[n]无序),找到该数组下所有的二元组合(a[i],a[j])其中0<=i<=j<n,满足条件a[i]*a[j]>=4或者a[i]*a[j]==0的所有组合列表,同时满足时间复杂度为O[n],空间复杂度为O[1].
如果如上推论是正确的话,那么后面就是算法的选择问题了。
1 通过数组A[i]和B[i]算出数组C[i]
2 排序C[i]数组,时间复杂度为O[n],如基数排序?
3 针对排序后的数据做如下操作,
3.1 找到这样一个下标i,使得C[i-1]<2,C[i]>=2,如这样一个数据[0,1.1,1.1,1.5,1.6,2,2.3,5,7,8,10],这样的好处就是,对于i以后的任何组合,你都可以确定他们满足C[i]*C[j]>=C[i]+C[j]。所以仅需要满足C[0]--C[i-1]到C[i]到C[n]的组合,满足条件C[i]*C[j]>=C[i]+C[j]。
3.2 分别定义连个小标i,j,使得i+1=j并且C[i]<2,C[j]>=2, 因为根据这样一个条件,如果C[i]*C[j]>=4,那么C[i]*C[k]>=4(k>j)肯定满足,同理如果C[i]*C[j]>=4不满足,那么C[k]*C[j]>=4(k<i)肯定也不满足.所以可以做一个循环分别计算C[0],C[i]之间各个参数满足条件的组合个数,计算出即可。
当然在3.2中你其实还是可以找到另外一个下标k使得C[k-1]<=1,C[k]>1,因为如果C[k]<=1,那么肯定不能满足这个组合条件了。2014年8月05日 10:09
-
这个题中只要 C[P]和C[Q]都是大于1的数那么
C[P]*C[Q]就是始终大于C[P]+C[Q]
( 即C[P]>=1&&C[Q]>=1 就会出现C[P]*C[Q]>=(C[P]+C[Q]))2014年8月04日 21:20
相关推荐
Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法...
JAVA经典算法面试39题及答案 本资源总结了39道经典的 JAVA 算法面试题目,每个题目都附带答案,涵盖了常见的算法问题,旨在帮助读者更好地掌握 JAVA 编程语言和算法设计。 算法概述 算法是计算机科学中最重要的...
java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法...
在这个“java常见算法题解析大全”中,你将找到一系列涵盖不同难度级别的算法问题,旨在帮助Java开发者提升技能,增强解决问题的能力。 首先,让我们了解一下折半查找(Binary Search)算法。这是一种在有序数组中...
JAVA算法编程题目及答案 本资源提供了50道JAVA算法编程题目及答案,涵盖了算法设计、数据结构、程序设计等多个方面的知识点。以下是对标题、描述、标签和部分内容的详细解释: 标题:JAVA算法编程题目及答案 本...
本压缩包包含了三个文档,分别是“JAVA经典算法40题.doc”、“最新JAVA编程题全集_50题及答案.doc”和“50道JAVA基础编程练习题.doc”,这些资源为初学者提供了大量的实践机会,有助于深入理解和运用Java。...
全排序、二分查找、冒泡排序、阶乘、最大公约数、最小公倍数、...这是里面包含的算法,本人在准备笔试的时候找的,算法尽量采用最优的。 所有的代码均经过测试,个人觉得没有问题,如果哪位大牛找到错误,欢迎批评指正
java算法题java算法题java算法题java算法题java算法题java算法题java算法题java算法题java算法题java算法题
JAVA算法编程题全集(50题及答案) 本资源提供了50道JAVA算法编程题,涵盖了基本数据结构、算法设计、面向对象编程等多方面内容,旨在检测JAVA语言的掌握情况。以下是对每道题目的知识点详细解释: 程序1:...
java算法题 java算法题 java算法题 java算法题java算法题
很不错的java算法题 很不错的java算法题 很不错的java算法题 很不错的java算法题 很不错的java算法题
"JAVA零基础算法练习题"就是针对这样的需求而设计的一系列练习题目,旨在帮助初学者提升对Java语言的理解和运用,同时培养解决问题的能力。 首先,让我们深入了解一下算法。算法是一系列精确的规则或步骤,用于解决...
Java经典算法50题,是Java开发者提升编程能力的重要练习资源。这50题涵盖了数据结构、排序算法、搜索算法等多个领域,旨在帮助程序员深化对基础理论的理解,并提高实际问题解决能力。通过解决这些题目,你可以熟悉并...
"JAVA经典算法90题【含源码】"的资源集合为Java初学者提供了一个绝佳的学习平台,旨在通过实际操作来理解和应用各种基础及进阶算法。下面将详细阐述这些算法题目所涉及的知识点,并建议的学习路径。 首先,"JAVA...
Java算法全卷涵盖了基本算法和图算法,是学习和提升编程技能的重要资源。这份资料主要针对使用Java语言进行算法实现的开发者,适用于那些对ANT、EJB、J2EE、JAVA和SPRING等技术栈有了解或兴趣的人群。下面我们将深入...
根据给定的信息,本文将对Java面试中常见的算法题进行详细的解析与总结,特别是针对冒泡排序和选择排序这两种基础但重要的排序算法。 ### 冒泡排序 #### 算法原理 冒泡排序是一种简单的排序算法。它重复地遍历要...
从给定的文件信息来看,标题“Java算法PDF版”暗示了这是一份关于Java编程语言中的算法应用和实现的资料。尽管描述部分没有提供太多具体的信息,仅表达了分享的意愿,但我们可以根据标题和可能包含的内容来深入探讨...
阅读《Java数据结构和算法 第二版》和解答《JAVA经典算法40题》可以帮助你深入理解和实践。同时,《JAVA面试题》提供了真实的面试场景,让你提前熟悉可能遇到的问题,提高应试能力。 总之,Java数据结构和算法是...
"JAVA经典算法90题【含源码】-史上最全"这个压缩包文件提供了一个宝贵的资源,涵盖了90个Java实现的经典算法问题,旨在帮助开发者提升算法思维和编程技巧。 1. **排序算法**:包括快速排序、归并排序、插入排序、...
【标题】"刷过的Java算法题源码仓库"所涉及的知识点主要集中在Java编程语言以及算法的应用上。这个标题暗示了这是一个包含多个Java实现的算法题目解决方案的集合,可能来自于像LeetCode、HackerRank这样的在线编程...