S******n 发帖数: 132 | 1 三个数组,从每个数组挑一个数a,b,c使得max(a-b,b-c,c-a)的值最小
这个是不是就是维持三个指针,每次计算最大和最小的差跟结果去比,比结果小就更新
,否则移动最小的指针,然后继续比较? | t****d 发帖数: 423 | 2 d从哪里来得
【在 S******n 的大作中提到】 : 三个数组,从每个数组挑一个数a,b,c使得max(a-b,b-c,c-a)的值最小 : 这个是不是就是维持三个指针,每次计算最大和最小的差跟结果去比,比结果小就更新 : ,否则移动最小的指针,然后继续比较?
| r**h 发帖数: 1288 | 3 我的想法是,先sort三个数组
然后每个数组从头开始比较三个数的差,然后每次将最小的那个元素的数组指针向后移
动一位。不知道有没有反例啊
run了一个代码看上去是正确的
def getMinDiffTriplet(a, b, c):
minDiff, ma, mb, mc = 9999, -1, -1, -1
pa, pb, pc = 0, 0, 0
while not (pa == len(a)-1 and pb == len(b)-1 and pc == len(c)-1):
na, nb, nc = a[pa], b[pb], c[pc]
curDiff = max(abs(na-nb), abs(na-nc), abs(nb-nc))
if curDiff < minDiff:
minDiff = curDiff
ma, mb, mc = na, nb, nc
if na<=nb and na<=nc:
if pa < len(a)-1:
pa += 1
else:
break
elif nb<=na and nb<=nc:
if pb < len(b)-1:
pb += 1
else:
break
else:
if pc < len(c)-1:
pc += 1
else:
break
return ma, mb, mc
import random
a = sorted([int(random.uniform(0, 100)) for i in range(15)])
b = sorted([int(random.uniform(0, 100)) for i in range(15)])
c = sorted([int(random.uniform(0, 100)) for i in range(15)])
print(a)
print(b)
print(c)
print(getMinDiffTriplet(a, b, c))
输出:
[7, 13, 25, 26, 31, 31, 50, 52, 52, 58, 58, 69, 71, 87, 96]
[3, 28, 28, 33, 38, 45, 46, 49, 67, 69, 71, 78, 84, 87, 98]
[17, 18, 21, 34, 36, 46, 53, 54, 65, 72, 79, 80, 82, 85, 93]
(71, 71, 72)
【在 S******n 的大作中提到】 : 三个数组,从每个数组挑一个数a,b,c使得max(a-b,b-c,c-a)的值最小 : 这个是不是就是维持三个指针,每次计算最大和最小的差跟结果去比,比结果小就更新 : ,否则移动最小的指针,然后继续比较?
| S******n 发帖数: 132 | 4 我的思路跟你一样除了sort这一步我觉得没有必要,你反正要遍历三个数组
【在 r**h 的大作中提到】 : 我的想法是,先sort三个数组 : 然后每个数组从头开始比较三个数的差,然后每次将最小的那个元素的数组指针向后移 : 动一位。不知道有没有反例啊 : run了一个代码看上去是正确的 : def getMinDiffTriplet(a, b, c): : minDiff, ma, mb, mc = 9999, -1, -1, -1 : pa, pb, pc = 0, 0, 0 : : while not (pa == len(a)-1 and pb == len(b)-1 and pc == len(c)-1): : na, nb, nc = a[pa], b[pb], c[pc]
| r**h 发帖数: 1288 | 5 不sort你怎么知道哪个数组的指针要往前呢
【在 S******n 的大作中提到】 : 我的思路跟你一样除了sort这一步我觉得没有必要,你反正要遍历三个数组
| J****3 发帖数: 427 | | S******n 发帖数: 132 | 7 我弄错了
【在 r**h 的大作中提到】 : 不sort你怎么知道哪个数组的指针要往前呢
|
|