本文介绍了在两个排序数组最近对总和的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
整数给定两个有序阵列, A 和 B ,和一个整数Ç ,我必须要找到 I,J 这样:
Given two sorted arrays of integers, a and b, and an integer c, I have to find i,j such that:
a[i] + b[j] <= c和 A [I] + B [J] 是越大越好。
我能想到的最好的办法是在 0 ( N 登录 N )的时间,即从第一个数组中的每个整数,寻找下界 CA [I] 的 任何人都可以给我建议一个更好的方式来做到这一点(也许在O( N )的时间)?
The best solution I can think of is in O(nlogn) time, taking every integer from first array and finding the lower bound of "c-a[i]". Can anyone suggest me a better way to do this (maybe in O(n) time)?
推荐答案思考了一下这个问题,那么你可以问自己: 是否有必要,每次排序的B-阵列连续值从[]中进行搜索?
Thinking a bit about it, then you could ask yourself: "Is it necessary, each time, to search in the sorted b-array for successive values from a[]?"
更多推荐
在两个排序数组最近对总和
发布评论