如何用python合并两个有序数组

本篇内容主要讲解“如何用python合并两个有序数组”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“如何用python合并两个有序数组”吧!

1. 两数之和

找出数组中两个数之和等于target的两数下标。

暴力枚举可以

但时间较长，时间复杂度$O(N^2)$

class Solution:     def twoSum(self, nums: List[int], target: int) -> List[int]:         n = len(nums)         for i in range(n):             for j in range(i + 1, n):                 if nums[i] + nums[j] == target:                     return [i, j]                  return []

哈希表

官方题解的一个比较巧妙的方式：使用哈希表（字典） 用字典记录出现过的数字的位置。 时间复杂度$O(N)$，空间复杂度$O(N)$

class Solution:     def twoSum(self, nums: List[int], target: int) -> List[int]:         hashtable = dict()         for i, num in enumerate(nums):             if target - num in hashtable:                 return [hashtable[target - num], i]             hashtable[nums[i]] = i         return []

2. 合并两个有序数组

两个有序数组，将第二个数组nums2合并到第一个数组nums1。

双指针

1.可以用双指针遍历两个数组：

class Solution:     def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:         """         Do not return anything, modify nums1 in-place instead.         """         # 两个中存在空数组的时，直接返回         if m == 0:             nums1[:] = nums2[:]             return         if n == 0:             return         index1,index2 = 0,0         t = []         while index1<m and index2<n:             if nums1[index1] <= nums2[index2]:                 t.append(nums1[index1])                 index1 += 1             else:                 t.append(nums2[index2])                 index2 += 1                   if index1 < m:             t += nums1[index1:m]         else:             t += nums2[index2:n]         nums1[:] = t[:]

官方版本，更简洁、清楚。

class Solution:     def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:         """         Do not return anything, modify nums1 in-place instead.         """         sorted = []         p1, p2 = 0, 0         while p1 < m or p2 < n:             if p1 == m:                 sorted.append(nums2[p2])                 p2 += 1             elif p2 == n:                 sorted.append(nums1[p1])                 p1 += 1             elif nums1[p1] < nums2[p2]:                 sorted.append(nums1[p1])                 p1 += 1             else:                 sorted.append(nums2[p2])                 p2 += 1         nums1[:] = sorted

（暴力） 追加后排序

2. 更简单粗暴的方式是直接将nums2追加到nums1后，进行排序。 及其简单而且效果很好。

class Solution:     def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:         """         Do not return anything, modify nums1 in-place instead.         """         nums1[m:] = nums2         nums1.sort()

到此，相信大家对“如何用python合并两个有序数组”有了更深的了解，不妨来实际操作一番吧！这里是亿速云网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！