乐趣区

关于golang:golangleetcode初级只出现一次的数字两个数组的交集Ⅱ

jiezi

第一题 只呈现一次的数字

题目

给定一个非空整数数组，除了某个元素只呈现一次以外，其余每个元素均呈现两次。找出那个只呈现了一次的元素。

阐明：

你的算法应该具备线性工夫复杂度。你能够不应用额定空间来实现吗？

示例 1:

输出: [2,2,1]
输入: 1
示例 2:

输出: [4,1,2,1,2]
输入: 4

解题思路

对于本题，初始解题思路是遍历数组，通过某个容器判断元素是否屡次呈现。
但题目要求了应用额定空间实现，那么咱们只能想方法在遍历数组的过程中通过运算消去雷同的元素，借鉴评论区，咱们找到了这样的一个运算

异或也叫半加运算，其运算法令相当于不带进位的二进制加法
其运算法令为

a b a⊕b
0 0 0
0 1 1
1 0 1
1 1 0

故对于任意的数 a，有
任何数和 00 做异或运算，后果依然是原来的数，即 a⊕0=a。
任何数和其本身做异或运算，后果是 00，即 a⊕a=0。

在 golang 语言中
^ 运算符有两个性能

1、作为二元运算符

^ 作二元运算符就是异或，包含符号位在内，雷同为 0，不雷同为 1

规定：1^1 =0, 0^0=0,1^0=1,0^1=1

2、作为一元运算符

^ 作一元运算符示意是按位取反，包含符号位在内
规定：1=0,0=1

复杂度剖析
工夫复杂度：O(n)，其中 n 是数组长度。只须要对数组遍历一次。
空间复杂度：O(1)。

代码

func singleNumber(nums []int) int {for _,i:=range nums[1:]{nums[0]=nums[0]^i
    }
    return nums[0]
}

第二题

题目

给你两个整数数组 nums1 和 nums2，请你以数组模式返回两数组的交加。返回后果中每个元素呈现的次数，应与元素在两个数组中都呈现的次数统一（如果呈现次数不统一，则思考取较小值）。能够不思考输入后果的程序。

 

示例 1：

输出：nums1 = [1,2,2,1], nums2 = [2,2]
输入：[2,2]
示例 2:

输出：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输入：[4,9]
 

提醒：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
 

进阶：

如果给定的数组曾经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小，哪种办法更优？
如果 nums2 的元素存储在磁盘上，内存是无限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

解题思路

题目给了两个数组，要遍历两个数组，查找其中的交加元素，很容易能想到通过双指针实现两个数组元素的比拟。但细读题目咱们发现。数组中的元素是无序且可反复的，无序意味着须要屡次的查找，可反复意味着屡次查找时对于后果有很大的烦扰性。所以咱们须要首先对数组进行排序，或者在找到雷同元素时将该元素移出数组，这就给算法设计带来了很高的复杂度

复杂度剖析
工夫复杂度：O(mlogm+nlogn)，其中 m 和 n 别离是两个数组的长度。对两个数组进行排序的工夫复杂度是 O(mlogm+nlogn)，遍历两个数组的工夫复杂度是 O(m+n)，因而总工夫复杂度是 O(mlogm+nlogn)。
空间复杂度：O(min(m,n))，其中 m 和 n 别离是两个数组的长度。为返回值创立一个数组 intersection，其长度为较短的数组的长度。

浏览官网思路，失去了复杂度更低的做法，首先将一个数组通过哈希表存储并记录数组元素的呈现次数，再通过查阅哈希表寻找两个数组的交加

办法一：哈希表
因为同一个数字在两个数组中都可能呈现屡次，因而须要用哈希表存储每个数字呈现的次数。对于一个数字，其在交集中呈现的次数等于该数字在两个数组中呈现次数的最小值。
援用
首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应呈现的次数，而后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字增加到答案，并缩小哈希表中该数字呈现的次数。
援用
为了升高空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应呈现的次数，而后遍历较长的数组失去交加。
援用
作者：LeetCode-Solution
链接：https://leetcode-cn.com/probl…
起源：力扣（LeetCode）
著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。
复杂度剖析

工夫复杂度：O(m+n)，其中 m 和 n 别离是两个数组的长度。须要遍历两个数组并对哈希表进行操作，哈希表操作的工夫复杂度是 O(1)，因而总工夫复杂度与两个数组的长度和呈线性关系。

空间复杂度：O(min(m,n))，其中 m 和 n 别离是两个数组的长度。对较短的数组进行哈希表的操作，哈希表的大小不会超过较短的数组的长度。为返回值创立一个数组 intersection，其长度为较短的数组的长度。

代码

func small(nums1 []int, nums2 []int) []int{if len(nums1)<len(nums2){return nums1}else{return nums2}
}
func big(nums1 []int, nums2 []int) []int{if len(nums1)<len(nums2){return nums2}else{return nums1}
}
func intersect(nums1 []int, nums2 []int) []int {m:=map[int]int{}
    for _,i:=range small(nums1,nums2){m[i]++
    }
    var list []int
    for _,num:=range big(nums1,nums2){if m[num]>0{list=append(list,num)
            m[num]--
        }
    }
    return list
}

代码优化

在官网代码中通过 通过递归调用 简化了对于较小数组的判断 使代码更为简洁好看

func intersect(nums1 []int, nums2 []int) []int {

**if len(nums1) > len(nums2) {return intersect(nums2, nums1)
}**
m := map[int]int{}
for _, num := range nums1 {m[num]++
}

intersection := []int{}
for _, num := range nums2 {if m[num] > 0 {intersection = append(intersection, num)
        m[num]--
    }
}
return intersection

}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/probl…
起源：力扣（LeetCode）
著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

退出移动版