FilesExpand file tree

 master

/

Contains Duplicate.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

58 lines (52 loc) · 1.29 KB

 master

/

Contains Duplicate.java

Copy path

Top

File metadata and controls

• Code
• Blame

58 lines (52 loc) · 1.29 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

57

58

E

1522012573

tags: Array, Hash Table

无序数组, 找是否有重复element, return true/false.

#### HashSet

- No brain: HashSet.

- Time O(n), Space O(n)

#### Sort, Binary Search

- Arrays.sort(x): Time O(nLogN), Space O(1)

- 排序后, 重复数会排在一起, 然后 binary search

```

/*

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array,

and it should return false if every element is distinct.

*/

/*

Use a hashSet. Cost: extra space.

*/

class Solution {

public boolean containsDuplicate(int[] nums) {

if (nums == null || nums.length == 0) {

return false;

}

final HashSet<Integer> set = new HashSet<>();

for (int num : nums) {

if (set.contains(num)) {

return true;

}

set.add(num);

}

return false;

}

}

/*

Sorry array, nLog(n)

*/

class Solution {

public boolean containsDuplicate(int[] nums) {

if (nums == null || nums.length == 0) {

return false;

}

Arrays.sort(nums);

for (int i = 0; i < nums.length - 1; i++) {

if (nums[i] == nums[i + 1]) {

return true;

}

}

return false;

}

}

```