LeetCode 刷题 Swift 两个数组的交集
<div id="navCategory"><h5 class="catalogue">目录</h5><ul class="first_class_ul"><li>题目</li><li>方法一：两个集合</li><ul class="second_class_ul"><li>思路及解法</li><li>代码</li><li>复杂度分析</li></ul><li>方法二：排序 + 双指针</li><ul class="second_class_ul"><li>思路及解法</li><li>代码</li><li>复杂度分析</li></ul></ul></div><p class="maodian"></p><h2>题目</h2><p>给定两个数组 <code>nums1</code> 和 <code>nums2</code>，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。</p>
<p><strong>示例 1：</strong></p>
<blockquote><p><strong>输入：</strong> nums1 = , nums2 = </p>
<p><strong>输出：</strong> </p></blockquote>
<p><strong>示例 2：</strong></p>
<blockquote><p><strong>输入：</strong> nums1 = , nums2 = </p>
<p><strong>输出：</strong> </p>
<p><strong>解释：</strong> 也是可通过的</p></blockquote>
<p class="maodian"></p><h2>方法一：两个集合</h2>
<p class="maodian"></p><p class="maodian"></p><h3>思路及解法</h3>
<p>计算两个数组的交集，直观的方法是遍历数组 <code>nums1</code>，对于其中的每个元素，遍历数组 <code>nums2</code> 判断该元素是否在数组 <code>nums2</code> 中，如果存在，则将该元素添加到返回值。假设数组 <code>nums1</code> 和 <code>nums2</code> 的长度分别是 m 和 n，则遍历数组 <code>nums1</code> 需要 O(m) 的时间，判断 <code>nums1</code> 中的每个元素是否在数组 <code>nums2</code> 中需要 O(n) 的时间，因此总时间复杂度是 O(mn)。</p>
<p>如果使用哈希集合存储元素，则可以在 O(1)的时间内判断一个元素是否在集合中，从而降低时间复杂度。</p>
<p>首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。该方法的时间复杂度可以降低到 O(m+n)</p>
<p class="maodian"></p><p class="maodian"></p><h3>代码</h3>
<div class="jb51code"><pre class="brush:cpp;">class Solution {
func intersection(_ nums1: , _ nums2: ) -> {
return set_intersection(Set(nums1), Set(nums2))
}
func set_intersection(_ set1: Set<Int>, _ set2: Set<Int>) -> {
if set1.count > set2.count {
return set_intersection(set2, set1)
}
var intersection: = []
for num in set1 {
if set2.contains(num) {
intersection.append(num)
}
}
return intersection
}
}
</pre></div>
<p class="maodian"></p><p class="maodian"></p><h3>复杂度分析</h3>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202209/20220921084747042.png" /></p>
<p class="maodian"></p><h2>方法二：排序 + 双指针</h2>
<h3>思路及解法</h3>
<p>如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。</p>
<p>首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量 pre\textit{pre}pre 表示上一次加入答案数组的元素。</p>
<p>初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于 pre\textit{pre}pre ，将该数字添加到答案并更新 pre\textit{pre}pre 变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。</p>
<h3>代码</h3>
<div class="jb51code"><pre class="brush:cpp;">class Solution {
func intersection(_ nums1: , _ nums2: ) -> {
let newNums1: = nums1.sorted()
let newNums2: = nums2.sorted()
let length1: Int = newNums1.count
let length2: Int = newNums2.count
var intersection: = []
var index1 = 0
var index2 = 0
while index1 < length1 && index2 < length2 {
let num1 = newNums1
let num2 = newNums2
if num1 == num2 {
if intersection.isEmpty || num1 != intersection.last {
intersection.append(num1)
}
index1 += 1
index2 += 1
} else if num1 < num2 {
index1 += 1
} else {
index2 += 1
}
}
return intersection
}
}
</pre></div>
<h3>复杂度分析</h3>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202209/20220921084747043.png" /></p>
<p>以上就是LeetCode 刷题 Swift 两个数组的交集的详细内容，更多关于Swift 两个数组交集的资料请关注琼殿技术社区其它相关文章！</p>
<div class="art_xg">
<b>您可能感兴趣的文章:</b><ul><li>java LeetCode刷题稍有难度的贪心构造算法</li><li>Java C++刷题leetcode1106解析布尔表达式</li><li>IntelliJ IDEA 刷题利器 LeetCode 插件详解</li><li>如何在Intellij中安装LeetCode刷题插件方便Java刷题</li><li>vscode中配置LeetCode插件的教程(愉快刷题)</li><li>leetcode刷题记录(最新推荐)</li></ul>
</div>
</div>
<!--endmain-->
頁:
[1]