测试角度
要说测试模型,对咱们程序员来说,那自然是写代码的能力强不强比较重要了。那么下面我们以 leetcode 中的一道表面上是困难题的题目来考考各家大模型,看看哪个才应该是咱们日常写程序的帮手。
部分模型回答
问题部分如下截图,后边就不再重复粘贴了,主要来看回答。我们注意到这里的难点在于在于对时间复杂度有要求,看看各个模型能不能注意到这一点。
出于篇幅,这里只贴出来结果比较好的几个模型进行点评。
Abab6.5 Chat (MiniMax) 结果
要找到两个正序数组的中位数,并且要求算法的时间复杂度为 O(log (m+n)),可以使用二分查找的方法。以下是一种可能的解决方案:
- 首先,确保
nums1
是较短的数组,如果不是,则交换nums1
和nums2
。 - 使用二分查找,在较短的数组
nums1
中查找合适的分割线,使得nums1
分割线左侧的元素和nums2
分割线右侧的元素个数之和等于nums1
分割线右侧的元素和nums2
分割线左侧的元素个数之和(或者相差1,如果总元素个数是奇数)。 - 通过比较
nums1
中分割线两侧的元素与nums2
中分割线两侧的元素,调整分割线的位置,直到找到正确的分割线位置。 - 根据分割线的位置,计算中位数。
下面是具体的算法实现:
def findMedianSortedArrays(nums1, nums2):
# 确保 nums1 是较短的数组
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
total_left = (m + n + 1) // 2
# 在 nums1 的区间 [0, m] 里查找恰当的分割线,
# 使得 nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]
left, right = 0, m
while left < right:
i = left + (right - left) // 2
j = total_left - i
if nums1[i] < nums2[j - 1]:
# i 需要增大
left = i + 1
else:
# i 需要减小
right = i
i = left
j = total_left - i
# 处理数组长度为奇数和偶数的情况
nums1_left_max = float('-inf') if i == 0 else nums1[i - 1]
nums2_left_max = float('-inf') if j == 0 else nums2[j - 1]
nums1_right_min = float('inf') if i == m else nums1[i]
nums2_right_min = float('inf') if j == n else nums2[j]
if (m + n) % 2 == 1:
return max(nums1_left_max, nums2_left_max)
else:
return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2
# 示例
nums1 = [1, 3]
nums2 = [2]
print(findMedianSortedArrays(nums1, nums2)) # 输出 2.0
nums1 = [1, 2]
nums2 = [3, 4]
print(findMedianSortedArrays(nums1, nums2)) # 输出 2.5
这个算法的时间复杂度是 O(log(min(m, n))),因为二分查找是在较短的数组上进行的。
Abab6.5 Chat (MiniMax) 点评
Abab6.5 Chat (MiniMax)给出的答案是python写的,估计训练使用python的代码比较多。模型注意到了时间复杂度,并且一直在强调,且给出的代码是可运行的,算法描述也比较清晰,代码的质量中规中矩,且加了注释,还不错。
Baichuan 4 (百川智能) 回答
为了找到两个有序数组的中位数,我们可以使用二分查找的方法来减少时间复杂度到O(log(min(m, n)))。以下是解决这个问题的步骤:
-
确保
nums1
是较短的数组,如果nums1
比nums2
长,交换它们。这样做是为了优化二分查找的性能。 -
在
nums1
上执行二分查找,找到适当的分割线,使得nums1
左边的元素和nums2
左边的元素一起组成了整个合并数组左边的一半,同时nums1
右边的元素和nums2
右边的元素组成右边的一半。 -
调整分割线,以确保左右两边的元素数量相等或最多相差一个,这取决于合并后数组长度的奇偶性。
-
计算中位数。如果合并后数组的长度是奇数,则中位数是两个数组左边部分的最大值。如果是偶数,则中位数是两个数组左边部分的最大值和两个数组右边部分的最小值的平均值。
下面是这个算法的Python代码实现:
def findMedianSortedArrays(nums1, nums2):
# 确保nums1是较短的数组
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
imin, imax, half_len = 0, m, (m + n + 1) // 2
while imin <= imax:
i = (imin + imax) // 2
j = half_len - i
if i < m and nums2[j-1] > nums1[i]:
# i太小,必须增加它
imin = i + 1
elif i > 0 and nums1[i-1] > nums2[j]:
# i太大,必须减小它
imax = i - 1
else:
# i正好
if i == 0: max_of_left = nums2[j-1]
elif j == 0: max_of_left = nums1[i-1]
else: max_of_left = max(nums1[i-1], nums2[j-1])
if (m + n) % 2 == 1:
return max_of_left
if i == m: min_of_right = nums2[j]
elif j == n: min_of_right = nums1[i]
else: min_of_right = min(nums1[i], nums2[j])
return (max_of_left + min_of_right) / 2.0
# 这种情况不应该发生,如果发生了说明输入有误
raise ValueError("Input arrays are not sorted or other error occurred")
# 示例
print(findMedianSortedArrays([1,3], [2])) # 输出: 2.00000
print(findMedianSortedArrays([1,2], [3,4])) # 输出: 2.50000
这段代码首先确保了nums1
是较短的数组,然后通过二分查找在nums1
上找到一个合适的索引i
,使得nums1
的前i
个元素和nums2
的前j
个元素共同构成了合并后数组的前一半。最后根据合并后数组长度的奇偶性来计算中位数。
Baichuan 4 (百川智能) 点评
我们看到,这里同样使用了python的解法,代码可运行,解法描述比较清晰,并且考虑到了错误处理,还是不错的。
ERNIE 4.0 8K 0329 (百度文心一言) 回答
要实现时间复杂度为 O(log(m+n)) 的算法来找到两个正序数组的中位数,可以使用二分查找的方法。但请注意,严格的 O(log(m+n)) 解决方案可能相当复杂。为了简化,如果我们允许一个稍微宽松的时间复杂度界限(例如,在某些情况下接近 O(log(min(m, n)))),我们可以采用一个更容易理解的方法。
下面是一个简化的方法,它基于二分查找,但并不是严格的 O(log(m+n)),而是更接近于 O(log(min(m, n))),因为它每次都在较短的数组上进行二分操作:
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1 # 确保 nums1 是较短的数组
m, n = len(nums1), len(nums2)
left, right = 0, m
while left <= right:
partitionX = (left + right) // 2 # 在 nums1 中的分割点
partitionY = ((m + n + 1) // 2) - partitionX # 在 nums2 中的分割点
# 确保左半部分都小于右半部分
maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
minRightX = float('inf') if partitionX == m else nums1[partitionX]
maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
minRightY = float('inf') if partitionY == n else nums2[partitionY]
if maxLeftX <= minRightY and maxLeftY <= minRightX:
# 已经找到了正确的划分
if (m + n) % 2 == 0:
return max(maxLeftX, maxLeftY, key=float) / 2 + min(minRightX, minRightY, key=float) / 2
else:
return max(maxLeftX, maxLeftY, key=float) # 总是取较大的左半部分作为中位数
elif maxLeftX > minRightY: # 太靠右,需要向左调整
right = partitionX - 1
else: # 太靠左,需要向右调整
left = partitionX + 1
# 如果未找到中位数,则抛出异常(实际上,由于我们的逻辑,这里不会被执行到)
raise ValueError("No median found")
# 示例测试
print(findMedianSortedArrays([1, 3], [2])) # 输出: 2.0
print(findMedianSortedArrays([1, 2], [3, 4])) # 输出: 2.5
这个算法通过二分查找确定两个数组中的分割点,以确保左半部分的所有元素都小于或等于右半部分的所有元素。然后,根据分割点找到中位数。注意,这个解决方案在数组长度不等的情况下也能正确工作,并且处理了总数组长度是奇数还是偶数的情况。
虽然这个解决方案的时间复杂度并不是严格的 O(log(m+n)),但在很多实际应用中,它的性能已经足够好,并且比严格的 O(log(m+n)) 解决方案更容易理解和实现。如果需要严格的 O(log(m+n)) 解决方案,请参考一些高级的二分查找变种,它们通常涉及更复杂的边界条件和分割逻辑。
ERNIE 4.0 8K 0329 (百度文心一言) 点评
文心一言给的也是python的回答,可见python确实是比较常用。文心一言没有给出具体的算法步骤,但代码注释和中文描述都很流畅易懂,比百川智能要稍强一些。
Hunyuan Pro (腾讯混元) 回答
为了实现 O(log(m+n)) 的时间复杂度,我们可以使用二分查找的方法。首先,我们需要找到两个数组中较短的那个数组,并将其作为二分查找的主体。假设较短数组为 A,长数组为 B,我们可以在 A 中进行二分查找,找到一个位置 partitionA
,使得 A 中有 partitionA
个元素在左侧,有 len(A) - partitionA
个元素在右侧。同时,我们需要在 B 中找到一个位置 partitionB
,使得 B 中有 partitionB
个元素在左侧,有 len(B) - partitionB
个元素在右侧。这样,我们可以保证左侧的所有元素都小于等于右侧的所有元素。
接下来,我们需要判断当前的分割是否满足条件。如果满足条件,我们就可以计算中位数。如果不满足条件,我们需要根据实际情况调整二分查找的范围。
以下是具体的算法步骤:
- 找到较短的数组 A 和长数组 B。
- 初始化二分查找的范围:
imin = 0
,imax = len(A)
。 - 进行二分查找:
a. 计算partitionA = (imin + imax) // 2
。
b. 计算partitionB = (len(A) + len(B) + 1) // 2 - partitionA
。
c. 判断当前分割是否满足条件:- 如果
partitionA > 0
且A[partitionA-1] > B[partitionB]
,说明当前分割过于右侧,需要将imax
更新为partitionA - 1
。 - 如果
partitionA < len(A)
且A[partitionA] < B[partitionB-1]
,说明当前分割过于左侧,需要将imin
更新为partitionA + 1
。 - 否则,当前分割满足条件,可以计算中位数。
- 如果
- 计算中位数:
- 如果
(len(A) + len(B))
是奇数,那么中位数为max(A[partitionA-1], B[partitionB-1])
。 - 如果
(len(A) + len(B))
是偶数,那么中位数为(max(A[partitionA-1], B[partitionB-1]) + min(A[partitionA], B[partitionB])) / 2
。
- 如果
以下是 Python 代码实现:
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
imin, imax, half_len = 0, m, (m + n + 1) // 2
while imin <= imax:
partitionA = (imax + imin) // 2
partitionB = half_len - partitionA
if partitionA > 0 and nums1[partitionA - 1] > nums2[partitionB]:
imax = partitionA - 1
elif partitionA < m and nums2[partitionB - 1] > nums1[partitionA]:
imin = partitionA + 1
else:
if partitionA == 0:
max_of_left = nums2[partitionB - 1]
elif partitionB == 0:
max_of_left = nums1[partitionA - 1]
else:
max_of_left = max(nums1[partitionA - 1], nums2[partitionB - 1])
if (m + n) % 2 == 1:
return max_of_left
if partitionA == m:
min_of_right = nums2[partitionB]
elif partitionB == n:
min_of_right = nums1[partitionA]
else:
min_of_right = min(nums1[partitionA], nums2[partitionB])
return (max_of_left + min_of_right) / 2
这个算法的时间复杂度为 O(log(min(m, n))),满足题目要求。
Hunyuan Pro (腾讯混元) 点评
腾讯混元给出了具体的思路和具体步骤,并给出了常规的python解答,还是不错的。
Mixtral 8x22B Instruct (Mistral) 回答
这个问题可以使用二分查找的思想来解决。
首先,我们需要找到两个数组的中位数,如果两个数组的长度之和为奇数,那么中位数就是中间那个数,如果为偶数,那么中位数就是中间两个数的平均值。
我们可以定义两个指针,分别指向两个数组的开头,然后我们可以不断地比较这两个指针所指向的数,将较小的那个数放入一个新的数组中,直到我们找到中位数。
具体实现如下:
def findMedianSortedArrays(nums1, nums2):
nums = nums1 + nums2
nums.sort()
length = len(nums)
if length % 2 == 0:
return (nums[length // 2] + nums[length // 2 - 1]) / 2
else:
return nums[length // 2]
这个实现的时间复杂度是 O(m+n),因为我们需要将两个数组合并成一个数组,然后排序,最后找到中位数。但是这个实现并不满足题目要求的时间复杂度为 O(log(m+n))。
为了满足题目要求的时间复杂度,我们可以使用二分查找的思想。具体实现如下:
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
x, y = len(nums1), len(nums2)
start = 0
end = x
while start <= end:
partitionX = (start + end) // 2
partitionY = ((x + y + 1) // 2) - partitionX
maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
minRightX = float('inf') if partitionX == x else nums1[partitionX]
maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
minRightY = float('inf') if partitionY == y else nums2[partitionY]
if maxLeftX <= minRightY and maxLeftY <= minRightX:
if (x + y) % 2 == 0:
return max(maxLeftX, maxLeftY), min(minRightX, minRightY)
else:
return max(maxLeftX, maxLeftY)
elif maxLeftX > minRightY:
end = partitionX - 1
else:
start = partitionX + 1
这个实现的时间复杂度是 O(log(min(m, n))),因为我们使用二分查找的思想,每次都将问题规模减半。
这个实现的基本思想是,我们需要找到两个数组的中位数,因此我们需要将这两个数组分成两部分,使得左半部分的最大值小于等于右半部分的最小值。如果左半部分的最大值大于右半部分的最小值,那么我们就需要将分割点向左移动,否则我们就需要将分割点向右移动。
当我们找到了分割点后,我们就可以根据两个数组的长度来判断中位数是左半部分的最大值还是右半部分的最小值。如果两个数组的长度之和为奇数,那么中位数就是左半部分的最大值,如果为偶数,那么中位数就是左半部分的最大值和右半部分的最小值的平均值。
Mixtral 8x22B Instruct (Mistral) 点评
Mistral给出了两个思路,并且给出了对应代码的解析,中文描述也很流畅。对于这个我不是很熟的模型,我感觉还是不错的。
Qwen Max 0428 (阿里通义千问)回答
这个问题可以通过使用二分查找算法来解决,以达到O(log(min(m, n)))的时间复杂度,而不是题目要求的O(log(m+n)),但这是解决此问题最有效的方法。下面是详细的解决方案:
首先,确定哪个数组作为“较小”的数组可以简化问题。我们希望在两个数组之间进行相等划分,因此将较小的数组作为分割操作的目标会更高效。如果m > n,就交换两个数组,确保nums1是两个数组中较小或相等的那个。
然后,我们定义一个函数findKthElement
用来寻找两个已排序数组中的第k小元素。这个函数的核心思想是使用二分查找法在nums1数组上找到一个位置i,使得nums1[i-1] <= nums2[k-i] && nums2[k-i-1] <= nums1[i]。这样,第k小的元素要么是nums1[i],要么是nums2[k-i],具体取决于它们的相对位置和值。
以下是该算法的Python实现:
def findMedianSortedArrays(nums1, nums2):
# 确保nums1是较短的数组
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
x, y = len(nums1), len(nums2)
low, high = 0, x
while low <= high:
partitionX = (low + high) // 2
partitionY = (x + y + 1) // 2 - partitionX
# 如果partitionX是0,说明我们已经超出了nums1的左侧边界,此时nums1[-1]相当于一个负无穷
maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
# 类似地处理nums1的右侧边界
minRightX = float('inf') if partitionX == x else nums1[partitionX]
maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
minRightY = float('inf') if partitionY == y else nums2[partitionY]
if maxLeftX <= minRightY and maxLeftY <= minRightX:
# 找到了正确的分区
if (x + y) % 2 == 0:
# 数组总长度为偶数
return max(maxLeftX, maxLeftY), min(minRightX, minRightY)
else:
# 数组总长度为奇数
return max(maxLeftX, maxLeftY)
elif maxLeftX > minRightY:
# 缩小nums1的右边界
high = partitionX - 1
else:
# 扩大nums1的左边界
low = partitionX + 1
# 上述逻辑应始终能找到答案,理论上不会执行到这一步
return None
这段代码实现了寻找两个有序数组中位数的功能,符合题目要求。注意,虽然这里的解释提到时间复杂度为O(log(min(m, n))),但实际解决问题的思路是正确的,且效率较高,满足题目的实际需求。
Qwen Max 0428 (阿里通义千问)点评
通义千问这个大家都比较熟悉了,它给出了思路和代码,并且代码有注释,但没有给测试用例,整体还是不错的。
测评总结
在这道题上,文中的各个模型都给出了不错的回答。从整体上来看,以下是各个模型在我心目中的排名:
- Mistral
- Qwen Max 0428
- 腾讯混元
- 百度文心一言
- MiniMax
- 百川智能