這篇文章主要介紹“Python如何求兩個(gè)數(shù)組的交集”的相關(guān)知識(shí)，小編通過(guò)實(shí)際案例向大家展示操作過(guò)程，操作方法簡(jiǎn)單快捷，實(shí)用性強(qiáng)，希望這篇“Python如何求兩個(gè)數(shù)組的交集”文章能幫助大家解決問(wèn)題。

我們提供的服務(wù)有：成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、微信公眾號(hào)開(kāi)發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、新鄉(xiāng)ssl等。為數(shù)千家企事業(yè)單位解決了網(wǎng)站和推廣的問(wèn)題。提供周到的售前咨詢(xún)和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的新鄉(xiāng)網(wǎng)站制作公司

題目:

給定兩個(gè)數(shù)組,編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算它們的交集。

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]

示例 2:

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]

說(shuō)明:

• 輸出結(jié)果中每個(gè)元素出現(xiàn)的次數(shù),應(yīng)與元素在兩個(gè)數(shù)組中出現(xiàn)的次數(shù)一致。

• 我們可以不考慮輸出結(jié)果的順序。

進(jìn)階:

• 如果給定的數(shù)組已經(jīng)排好序呢?你將如何優(yōu)化你的算法?

• 如果 nums1 的大小比 nums2 小很多,哪種方法更優(yōu)?

• 如果 nums2 的元素存儲(chǔ)在磁盤(pán)上,磁盤(pán)內(nèi)存是有限的,并且你不能一次加載所有的元素到內(nèi)存中,你該怎么辦?

解題思路:

暴力解題就不說(shuō)了。

• 哈希表:利用哈希映射求得其中一個(gè)數(shù)組每個(gè)數(shù)字出現(xiàn)的頻次。遍歷另一個(gè)數(shù)組,每遇到相同數(shù)字,其存儲(chǔ)頻次減一,若頻次為 0,則移出哈希映射。如:

輸入 nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4 }計(jì)算 nums1 頻次: { 4:1, 9:1, 5:1 },Key = {4 , 9, 5 }遍歷 nums2:9 存在于 Key,9 頻次 -1 為 0,9 移出 HashMap:{ 4:1, 5:1 }4 存在于 Key,4 頻次 -1 為 0,4 移出 HashMap:{ 5:1 }9 不存在于 Key,跳過(guò)8 不存在于 Key,跳過(guò)...輸出:{9, 4}

• 雙指針:先把兩個(gè)數(shù)組排序,定義兩個(gè)指針 i, j ,移動(dòng)指針

如果 nums1 [i] == nums2 [j],則該數(shù)共有。

如果不等,則移動(dòng)元素值小的指針。

如：

輸入 nums1 = [ 4, 9, 5 ], nums2 = [ 9, 4, 9, 8, 4 ]
排序 nums1 = [ 4, 5, 9 ], nums2 = [ 4, 4, 8, 9, 9 ]
雙指針遍歷：[ 4, 5, 9]，[ 4, 4, 8, 9, 9 ]
 ^ ^
 4 = 4, 存入 res = [4], 移動(dòng)雙指針: [ 4, 5, 9]，[ 4, 4, 8, 9, 9 ]
 ^ ^
5 > 4, 移動(dòng)指向 4 的指針:[ 4, 5, 9]，[ 4, 4, 8, 9, 9 ]
 ^ ^
5 < 8, 移動(dòng)指向 5 的指針:[ 4, 5, 9]，[ 4, 4, 8, 9, 9 ]
 ^ ^
9 > 8, 移動(dòng)指向 8 的指針:[ 4, 5, 9]，[ 4, 4, 8, 9, 9 ]
 ^ ^
9 = 9, 存入 res = [4, 9], 移動(dòng)雙指針: [ 4, 5, 9 ]，[ 4, 4, 8, 9, 9 ]
 ^ ^
超過(guò) nums1 長(zhǎng)度，結(jié)束，返回 res

回答進(jìn)階問(wèn)題:

1. 雙指針?lè)ㄖ饕臅r(shí)操作就是排序操作的排序算法。對(duì)于有序數(shù)組當(dāng)然使用雙指針解題。

2. 在一個(gè)數(shù)組長(zhǎng)度遠(yuǎn)小于另一個(gè)數(shù)組時(shí),哈希表解題更優(yōu),只需哈希統(tǒng)計(jì)長(zhǎng)度較小的數(shù)組的元素頻次,遍歷長(zhǎng)數(shù)組即可。時(shí)間復(fù)雜度取決于長(zhǎng)數(shù)組長(zhǎng)度。如果用雙指針?lè)?對(duì)長(zhǎng)數(shù)組的排序?qū)⑾母鄷r(shí)間。

3. 如果內(nèi)存有限,只能選擇雙指針?lè)ɑ虮┝ζ平?無(wú)需額外空間復(fù)雜度。使用哈希表時(shí)在最壞情況下:每個(gè)數(shù)字只出現(xiàn)一次,HashMap 元素頻次統(tǒng)計(jì)后,其大小可能大于內(nèi)存容量。

哈希表解題:

Java:

class Solution {
 public int[] intersect(int[] nums1, int[] nums2) {
 HashMap<Integer, Integer> map = new HashMap<>();
 List<Integer> list = new ArrayList<>();//動(dòng)態(tài)數(shù)組
 for (Integer num : nums1) map.put(num, map.getOrDefault(num, 0) + 1);//統(tǒng)計(jì)元素出現(xiàn)頻次
 for (Integer num : nums2) {//遍歷另一個(gè)數(shù)組
 if (map.containsKey(num)) {
 int tmp = map.get(num)-1;//頻次減一
 if (tmp == 0) map.remove(num);//頻次為 0 時(shí),移出 HashMap
 else map.put(num, tmp);//否則更新頻次
 list.add(num);//加入動(dòng)態(tài)數(shù)組
 }
 }
 //轉(zhuǎn)為數(shù)組并返回
 int size=list.size();
 int[] res = new int[size];
 for (int i = 0; i < size; i++) res[i] = list.get(i);
 return res;
 }}

Python:

class Solution:
 def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
 count = dict(collections.Counter(nums1))# 自帶庫(kù)統(tǒng)計(jì)元素出現(xiàn)頻次,并轉(zhuǎn)為 Dict 類(lèi)型
 res = []
 for num in nums2:# 遍歷另一個(gè)數(shù)組
 if num in count:
 count[num] -= 1# 詞頻減一
 res.append(num)
 if count[num] <= 0:# 詞頻為 0 時(shí),移出字典
 count.pop(num)
 return res

雙指針解題:

Java:

class Solution {
 public int[] intersect(int[] nums1, int[] nums2) {
 List<Integer> list = new ArrayList<>();
 Arrays.sort(nums1);//排序數(shù)組
 Arrays.sort(nums2);
 int i = 0, j = 0;//定義指針
 while (i < nums1.length && j < nums2.length) {
 if (nums1[i] < nums2[j]) i++;//移動(dòng)較小數(shù)的指針
 else if (nums1[i] > nums2[j]) j++;//移動(dòng)較小數(shù)的指針
 else {
 //兩數(shù)相等則為交集,存入動(dòng)態(tài)數(shù)組,移動(dòng)雙指針
 list.add(nums1[i]);
 i++;
 j++;
 }
 }
 //轉(zhuǎn)為數(shù)組并返回
 int[] res = new int[list.size()];
 for (int k = 0; k < list.size(); k++) res[k] = list.get(k);
 return res;
 }}

Python:

class Solution:
 def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
 i, j, nums1_size, nums2_size = 0, 0, len(nums1), len(nums2)# 定義指針,計(jì)算數(shù)組長(zhǎng)度
 nums1, nums2, res = sorted(nums1), sorted(nums2), []# 排序數(shù)組,初始化返回?cái)?shù)組 res
 while i < nums1_size and j < nums2_size:# 循環(huán)條件為指針不溢出
 if nums1[i] < nums2[j]:# 移動(dòng)數(shù)值較小的指針
 i += 1
 elif nums1[i] > nums2[j]:# 移動(dòng)數(shù)值較小的指針
 j += 1
 else:
 res.append(nums1[i])# 數(shù)值相等,則為交集,移動(dòng)雙指針
 i += 1
 j += 1
 return res

關(guān)于“Python如何求兩個(gè)數(shù)組的交集”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。

網(wǎng)頁(yè)名稱(chēng)：Python如何求兩個(gè)數(shù)組的交集
本文路徑：http://aaarwkj.com/article42/jeisec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、網(wǎng)站維護(hù)、域名注冊(cè)、App開(kāi)發(fā)、外貿(mào)網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)