|
1 | 1 | packageeasy; |
2 | 2 |
|
| 3 | +importjava.util.Arrays; |
3 | 4 | importjava.util.HashSet; |
4 | 5 | importjava.util.Iterator; |
5 | 6 | importjava.util.Set; |
|
19 | 20 | publicclassIntersectionOfTwoArrays { |
20 | 21 |
|
21 | 22 | //then I clicked its Tags, and find it's marked with so many tags: Binary Search, HashTable, Two Pointers, Sort, now I'll try to do it one by one |
22 | | - |
| 23 | +//inspired by this post: https://discuss.leetcode.com/topic/45685/three-java-solutions |
| 24 | +publicint[]intersection_two_pointers(int[]nums1,int[]nums2) { |
| 25 | + |
| 26 | +} |
| 27 | + |
| 28 | +publicint[]intersection_binary_search(int[]nums1,int[]nums2) { |
| 29 | +//this approach is O(nlgn) |
| 30 | +Arrays.sort(nums1); |
| 31 | +Arrays.sort(nums2); |
| 32 | +Set<Integer>intersect =newHashSet(); |
| 33 | +for(inti :nums1){ |
| 34 | +if(binarySearch(i,nums2)){ |
| 35 | +intersect.add(i); |
| 36 | +} |
| 37 | +} |
| 38 | +int[]result =newint[intersect.size()]; |
| 39 | +Iterator<Integer>it =intersect.iterator(); |
| 40 | +for(inti =0;i <intersect.size();i++){ |
| 41 | +result[i] =it.next(); |
| 42 | +} |
| 43 | +returnresult; |
| 44 | +} |
| 45 | + |
| 46 | +privatebooleanbinarySearch(inti,int[]nums) { |
| 47 | +intleft =0,right =nums.length-1; |
| 48 | +while(left <=right){ |
| 49 | +intmid =left + (right-left)/2; |
| 50 | +if(nums[mid] ==i){ |
| 51 | +returntrue; |
| 52 | +}elseif(nums[mid] >i){ |
| 53 | +right =mid-1; |
| 54 | +}else { |
| 55 | +left =mid+1; |
| 56 | +} |
| 57 | +} |
| 58 | +returnfalse; |
| 59 | +} |
| 60 | + |
| 61 | +//tried a friend's recommended approach, didn't finish it to get it AC'ed, turned to normal approach as above and got it AC'ed. |
| 62 | +privatebooleanbinarySearch_not_working_version(inti,int[]nums) { |
| 63 | +if(nums ==null ||nums.length ==0)returnfalse; |
| 64 | +intleft =0,right =nums.length-1; |
| 65 | +while(left+1 <right){ |
| 66 | +intmid =left + (right-left)/2; |
| 67 | +if(nums[mid] >i){ |
| 68 | +right =mid; |
| 69 | +}elseif(nums[mid] <1){ |
| 70 | +left =mid; |
| 71 | +}elseif(nums[mid] ==i){ |
| 72 | +returntrue; |
| 73 | +}else { |
| 74 | +returnfalse; |
| 75 | +} |
| 76 | +} |
| 77 | +returnnums[left] ==i ||nums[right] ==i; |
| 78 | +} |
| 79 | + |
| 80 | +publicstaticvoidmain(String...strings){ |
| 81 | +IntersectionOfTwoArraystest =newIntersectionOfTwoArrays(); |
| 82 | +int[]nums1 =newint[]{1,2}; |
| 83 | +int[]nums2 =newint[]{2,1}; |
| 84 | +test.intersection_binary_search(nums1 ,nums2); |
| 85 | +} |
| 86 | + |
| 87 | +publicint[]intersection_two_hashsets(int[]nums1,int[]nums2) { |
| 88 | +//this approach is O(n) |
| 89 | +Set<Integer>set1 =newHashSet(); |
| 90 | +for(inti =0;i <nums1.length;i++){ |
| 91 | +set1.add(nums1[i]); |
| 92 | +} |
| 93 | +Set<Integer>intersect =newHashSet(); |
| 94 | +for(inti =0;i <nums2.length;i++){ |
| 95 | +if(set1.contains(nums2[i])){ |
| 96 | +intersect.add(nums2[i]); |
| 97 | +} |
| 98 | +} |
| 99 | +int[]result =newint[intersect.size()]; |
| 100 | +Iterator<Integer>it =intersect.iterator(); |
| 101 | +for(inti =0;i <intersect.size();i++){ |
| 102 | +result[i] =it.next(); |
| 103 | +} |
| 104 | +returnresult; |
| 105 | +} |
23 | 106 |
|
24 | 107 | //so naturally, I come up with this naive O(n^2) solution and surprisingly it got AC'ed immediately, no wonder it's marked as EASY. |
25 | 108 | publicint[]intersection_naive(int[]nums1,int[]nums2) { |
|