首页 > 代码库 > Array 数组类型题目笔记
Array 数组类型题目笔记
将小数组归并到大数组里
Merge Sorted Array
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Example
A = [1, 2, 3, empty, empty], B = [4, 5]
After merge, A will be filled as [1, 2, 3, 4, 5]
2点需要注意的：
1. inplace merge，从后往前走
2. 3个while 循环的控制条件
1. a != null && b != null
2. a != null
3. b != null
看似简单，反正我没写出来
class Solution { public void mergeSortedArray(int[] A, int m, int[] B, int n) { // write your code here int total = m + n - 1; int index1 = m - 1; int index2 = n - 1; while (index1 >= 0 && index2 >= 0) { if (A[index1] >= B[index2]) { A[total--] = A[index1--]; } else { A[total--] = B[index2--]; } } while (index2 >= 0) { A[total--] = B[index2--]; } while (index1 >= 0) { A[total--] = A[index1--]; } }}
---------------------------------分割线-----------------------------------
两个数组的交
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
方法1: hashset 为了去重，果然需要2个set
另外，为了把第二个set里的结果转化为数组，还需要第三个for循环
Time = O(n).
Space = O(n).
1 public class Solution { 2 public int[] intersection(int[] nums1, int[] nums2) { 3 HashSet<Integer> set1 = new HashSet<Integer>(); 4 for(int i: nums1){ 5 set1.add(i); 6 } 7 8 HashSet<Integer> set2 = new HashSet<Integer>(); 9 for(int i: nums2){10 if(set1.contains(i)){11 set2.add(i);12 }13 }14 15 int[] result = new int[set2.size()];16 int i = 0;17 for(int n: set2){18 result[i++] = n;19 }20 return result;21 }22 }
方法2: sort+ 2个指针
我们还可以使用两个指针来做，先给两个数组排序，然后用两个指针分别指向两个数组的开头，然后比较两个数组的大小，把小的数字的指针向后移，如果两个指针指的数字相等，那么看结果res是否为空，如果为空或者是最后一个数字和当前数字不等的话，将该数字加入结果res中，参见代码如下：
public class Solution { public int[] intersection(int[] nums1, int[] nums2) { if (nums1 == null || nums1.length == 0) { return nums1; } if (nums2 == null || nums2.length == 0) { return nums2; } Arrays.sort(nums1); Arrays.sort(nums2); int i, j; int size1 = nums1.length; int size2 = nums2.length; ArrayList<Integer> res = new ArrayList<Integer>(); for (i = 0, j = 0 ; i < size1 && j < size2;) { if (nums1[i] == nums2[j]) { if ((!res.isEmpty() && nums1[i] != res.get(res.size() - 1)) || res.isEmpty()) { res.add(nums1[i]); } i++; j++; } else if (nums1[i] > nums2[j]) { j++; } else { i++; } } int[] result = new int[res.size()]; i = 0; for (int temp : res) { result[i++] = temp; } return result; }}
方法3： sort 2个array 然后遍历nums1，用binary search 来查找
Arrays.binarySearch(nums2, nums1[i])) 666还能这么玩
public class Solution { public int[] intersection(int[] nums1, int[] nums2) { if (nums1 == null || nums1.length == 0) { return nums1; } if (nums2 == null || nums2.length == 0) { return nums2; } Arrays.sort(nums1); Arrays.sort(nums2); int size1 = nums1.length; ArrayList<Integer> res = new ArrayList<Integer>(); for (int i = 0; i < size1; i++) { if (i == 0 || nums1[i] != nums1[i - 1]) { if ((Arrays.binarySearch(nums2, nums1[i])) > -1) { res.add(nums1[i]); } } } int[] result = new int[res.size()]; int i = 0; for (int temp : res) { result[i++] = temp; } return result; }}
---------------------------------分割线-----------------------------------
快速排序系列 http://www.cnblogs.com/jiangchen/p/5935651.html
---------------------------------分割线-----------------------------------
股票问题，prefix sum运用，序列型动态规划 详见
http://www.cnblogs.com/jiangchen/p/5820378.html
---------------------------------分割线-----------------------------------
subarray 问题
Array 数组类型题目笔记