1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| //You are given two lists. Write a method that checks for duplicate elements in the second list.
// test cases :
// listA: [1,2,3,4]
// listB: [3,6,8.5]
//
// invalidList: [1,2,3,3]
// hasDupliactes(listA, listB) -> true
//boolean
// list sorted?
// O(lenA * LenB)
// hashset
// sort A , sort B
// and do binary search
// O(logn)
// hashset
// set add List A into set , no duplicate in list A
// continue add ListB into set , if duplicate one , set will failed. return false
// O(len A + len B)
// use two LinkedHashSet
// Add list A into set 1
// Add list B into set 2
// Add element from set2 into set 1
import java.util.*;
import java.util.HashSet;
public class FindDuplicate {
public static void main(String[] args) {
Integer[] array1 = { 1, 2, 3, 4};
Integer[] array2 = {3, 6, 8, 5};
FindDuplicate finder = new FindDuplicate();
System.out.println(finder.checkDuplicate(array1, array2));
}
public boolean checkDuplicate(Integer[] array1, Integer[] array2) {
Set<Integer> set1 = new HashSet<Integer>(Arrays.asList(array1));
Set<Integer> set2 = new HashSet<Integer>(Arrays.asList(array2));
// if set2.size() > set1.size()
for (int element : set2) {
if (!set1.add(element)) {
return true;
}
}
return false;
}
// second solution
// int pointA // pointer
}
|