iteye_3493 2014-08-04 06:28
浏览 242
已采纳

被一道JAVA算法题难住了,请各位帮忙看下。

数组 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), 不包括参数的存储空间.

  • 写回答

2条回答 默认 最新

  • ieanwfg201 2014-08-05 10:09
    关注

    分析如下:
    从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=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,如这样一个数据[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[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,那么肯定不能满足这个组合条件了。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥60 补全networkx TODO部分。
  • ¥15 有内推吗,云计算linux运维方向
  • ¥30 sort cuteSV.vcf by bcftools用IGV可视化出现报错
  • ¥100 SOS!对STK中导出的天体图像进行质心提取有没有人做过啊
  • ¥15 python 欧式距离
  • ¥15 运行qteasy报错
  • ¥15 遗传算法解决有工序顺序约束的大规模FJSP问题
  • ¥15 企业消防水炮塔设计方案
  • ¥20 WORKBENCH网格划分
  • ¥60 急招师兄远程解决下载NPCAP的BUG!