Median of Two Sorted Arrays
Merge 2 sorted arrays
Intersection of Two Arrays
主要问题就是 i 指针和 j 指针
like A对应 i 指针，B对应 j 指针
不要写乱 写着写着可能走神就写的不对应了 这种题不难 就怕你数组越界 一般都是 i, j 指针的问题
Merge Sorted Array
Example
A = [1, 2, 3, empty, empty], B = [4, 5]
After merge, A will be filled as [1, 2, 3, 4, 5]
这道题，两个数组已经是sorted的了，只是有个数组在后面有更多的空位
要倒着赋值 O(n)
正着的话每次移动整个数组都是O(n)的 worse case O(n^2)
public void mergeSortedArray(int[] A, int m, int[] B, int n) {
//把m - 1和n - 1单独赋给 i 和 j ，在接下来写程序的时候更好看，更好理解
int i = m - 1;
int j = n - 1;
int index = m + n - 1;
while (i >= 0 && j >= 0) {
if (A[i] > B[j]) {
A[index--] = A[i--];
} else {
A[index--] = B[j--];
}
}
while (i >= 0) {
A[index--] = A[i--];
}
while (j >= 0) {
A[index--] = B[j--];
}
}
下面的题目同理也是 i , j 指针的问题
Merge 2 sorted arrays
public int[] mergeSortedArray(int[] A, int[] B) {
if (A == null || B == null) {
return null;
}
int[] res = new int[A.length + B.length];
//while没有像for一样的现场赋值for(int i....)，while都是提前赋好值的
int i = 0, j = 0, index = 0;
while (i < A.length && j < B.length) {
if (A[i] < B[j]) {
res[index++] = A[i++];
} else {
res[index++] = B[j++];
}
}
while (i < A.length) {
res[index++] = A[i++];
}
while (j < B.length) {
res[index++] = B[j++];
}
return res;
}
Intersection of Two Arrays
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
一、HashSet version
遍历HashSet方法
1.迭代遍历：
Set<String> set = new HashSet<String>();
Iterator<String> it = set.iterator();
while (it.hasNext()) {
String str = it.next();
System.out.println(str);
}
2.for循环遍历：
for (String str : set) {
System.out.println(str);
}
HashSet version
Time:O(m + n)
Space:O(min(m, n))挑小一点的数组放到hashSet
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;
}
Set<Integer> hash = new HashSet<>();
for (int i = 0; i < nums1.length; i++) {
hash.add(nums1[i]);
}
Set<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[] res = new int[size];
int index = 0;
for (Integer num : resultHash) {
res[index++] = num;
}
return res;
}
};
Version 2: sort & merge
Time: O(nlogn + mlogm + m + n)
Space: O(1)
数据结构：2 pointers
这种方法先排序
[1, 1, 2, 2]和[2, 2]
两根指针从左往右扫，nums1[i] < nums2[j] 那么i++，看看下一个是否相等
nums1[i] > nums2[j] 那么j++
相等的话 如果没有重复就放进新的数组,之后要注意i , j的自增
一开始我们并不知道数组有多大，从nums1和nums2的长度里随便挑一个
以加入的intersection元素的个数再导入到另一个新数组中，perfect!
public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);//mlogm
Arrays.sort(nums2);//nlogn
int i = 0, j = 0;
int[] temp = new int[nums1.length];
int index = 0;
//这里的时间复杂度是m + n
while (i < nums1.length && j < nums2.length) {
if (nums1[i] == nums2[j]) {
if (index == 0 || temp[index - 1] != nums1[i]) {
temp[index++] = nums1[i];
}
//注意这里！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;
}
version 3: sort & binary search
这种方法先将nums1排序，然后对nums2中的每个元素，在nums1中二分查找，找到了放入HashSet中，再折腾进数组
假设nums1.length = m
nums2.length = n
假设n < m 那么久QuickSort小的那个,也就是n
Time: O(nlogn +mlogn) = (m + n)logn
Space: O(n)
public class Solution {
/*
* @param nums1: an integer array
* @param nums2: an integer array
* @return: an integer array
*/
public int[] intersection(int[] nums1, int[] nums2) {
// write your code here
if (nums1 == null || nums2 == null) {
return null;
}
Set<Integer> hash = new HashSet<>();
Arrays.sort(nums1);//nlogn
for (int i = 0; i < nums2.length; i++) {//mlogn
if (set.contains(nums2[i])) {
continue;
}
if(binarySearch(nums2[i], nums1)) {
hash.add(nums2[i]);
}
}
int size = hash.size();
int[] res = new int[size];
int index = 0;
for (Integer num : hash) {
res[index++] = num;
}
return res;
}
private boolean binarySearch(int target, int[] num) {
if (num == null || num.length == 0) {
return false;
}
int start = 0;
int end = num.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (num[mid] == target) {
return true;
} else if (num[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (num[start] == target) {
return true;
}
if (num[end] == target) {
return true;
}
return false;
}
};
Median of Two Sorted Arrays
“There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.”
The overall run time complexity should be O(log (m+n)).
如果k是中点，那么k = (m+n)/2
则logk就是O(log (m+n))了
这道题看懂就可以了 我不追求会写了：）
把这道题general成kth of 2 sorted arrays
因为要求log的时间复杂度,所以每次去掉一半，即去掉k/2, 两个分别排序的数组，怎么去掉k/2个元素呢？
其实直接去掉A,B数组之一的k/2就可以了，比较一下A，B分别在k/2的值是多少，去掉小的那个数组的前k/2
如果数组非常短都没有k/2的index,用MAX_VALUE代替，反正比的是谁小
如果数组一个数都没有了，就去找另一个数组的第k个数
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int len = A.length + B.length;
//奇数个:中间
if (len % 2 == 1) {
return findKth(A, 0, B, 0, len / 2 + 1);
}
//偶数个, 是除以2.0, 否则取整了
return (findKth(A, 0, B, 0, len / 2) + findKth(A, 0, B, 0, len / 2 + 1)) / 2.0;
}
private static int findKth(int[] A, int A_start, int[] B, int B_start, int k) {
//A数组一个都没有了
//k如果等于2,那么B_start = 0, (k - 1) = 1-----到k正好是第二个数
if (A_start >= A.length) {
return B[B_start + k - 1];
}
//B数组一个都没有了
if (B_start >= B.length) {
return A[A_start + k - 1];
}
//k down to 1, return两个数组中比较小的那个数
if (k == 1) {
return Math.min(A[A_start], B[B_start]);
}
//看A数组够不够长
int A_key;
//为什么要 - 1 呢?
//因为A_start + k / 2 - 1就是从A_start开始的第k/2个数，是一个index
if (A_start + k / 2 - 1 < A.length) {
A_key = A[A_start + k / 2 - 1];
} else {
A_key = Integer.MAX_VALUE;
}
int B_key;
if (B_start + k / 2 - 1 < B.length) {
B_key = B[B_start + k / 2 - 1];
} else {
B_key = Integer.MAX_VALUE;
}
if (A_key < B_key) {
//用k - k / 2而不用k/2是因为除法有个取整的问题，本题是去掉k/2个元素
//例如: k = 3, k/2 =1 然而k-k/2 = 2
return findKth(A, A_start + k / 2, B, B_start, k - k / 2);
} else {
return findKth(A, A_start, B, B_start + k / 2, k - k / 2);
}
}
}
