描述
返回两个数组的交
注意事项
Each element in the result must be unique.
The result can be in any order.
样例
nums1 =
[1, 2, 2, 1], nums2 =[2, 2], 返回[2].
可以用三种不同的方法实现吗？
时间复杂度空间复杂度搞不清楚
思路
- 排序找相同元素
- 结果的去重
代码
- sort & merge
时间复杂度O(nlogn + mlogm)
空间复杂度O(1)
public class Solution {
/**
* @param nums1 an integer array
* @param nums2 an integer array
* @return an integer array
*/
public int[] intersection(int[] nums1, int[] nums2) {
// 先排序
Arrays.sort(nums1);
Arrays.sort(nums2);
int i = 0, j = 0;
int[] temp = new int[nums1.length];
int index = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] == nums2[j]) {
// index等于0情况(防止index - 1越界)以及结果的去重
if (index == 0 || temp[index - 1] != nums1[i]) {
temp[index++] = nums1[i];
}
// 注意i++， j++的位置，在满足相等情况却和已有结果重复时，也要向后移动 i 和 j
i++;
j++;
} else if (nums1[i] < nums2[j]) {
i++;
} else {
j++;
}
}
int[] result = new int[index];
for (int k = 0; k < index; k++) {
result[k] = temp[k];
}
return result;
}
}
- hash map
时间复杂度O(n + m)
空间复杂度O(min(n, m))
public class Solution {
/**
* @param nums1 an integer array
* @param nums2 an integer array
* @return an integer array
*/
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return null;
}
HashSet<Integer> hash = new HashSet<>();
for (int i = 0; i < nums1.length; i++) {
hash.add(nums1[i]);
}
HashSet<Integer> resultHash = new HashSet<>();
for (int i = 0; i < nums2.length; i++) {
// 结果的去重
if (hash.contains(nums2[i]) && !resultHash.contains(nums2[i])) {
resultHash.add(nums2[i]);
}
}
int size = resultHash.size();
int[] result = new int[size];
int index = 0;
for (Integer num : resultHash) {
result[index++] = num;
}
return result;
}
}
- sort & binary search
时间复杂度O(nlogn + mlogn)
空间复杂度O(1)
public class Solution {
/**
* @param nums1 an integer array
* @param nums2 an integer array
* @return an integer array
*/
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return null;
}
HashSet<Integer> set = new HashSet<>();
Arrays.sort(nums1);
for (int i = 0; i < nums2.length; i++) {
if (set.contains(nums2[i])) {
continue;
}
if (binarySearch(nums1, nums2[i])) {
set.add(nums2[i]);
}
}
int[] result = new int[set.size()];
int index = 0;
for (Integer num : set) {
result[index++] = num;
}
return result;
}
private boolean binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}
int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = (end - start) / 2 + start;
if (nums[mid] == target) {
return true;
}
if (nums[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (nums[start] == target) {
return true;
}
if (nums[end] == target) {
return true;
}
return false;
}
}
