FilesExpand file tree

 master

/

offer03.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

94 lines (87 loc) · 3.04 KB

 master

/

offer03.java

Copy path

Top

File metadata and controls

• Code
• Blame

94 lines (87 loc) · 3.04 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

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

import java.util.Arrays;

/**

* [03] 数组中重复的数字

*

* 题目：找出数组中重复的数字

*

* 在一个长度为 n 的数组里的所有数字都在 0 到 n - 1 的范围内，数组中某些数字是重复的，找出数组中任意一个重复的数字。

* （不知道有几个数字是重复的；也不知道每个数字重复几次）

*

* 思路：1。将输入数组排序，从排序的数组中找到重复的数字。

* 2。使用哈希表（字符集小的时候可以使用数组）存储已遍历过的数字，若当前遍历的数字出现过，则找到重复数字。

* 3。遍历数组，将数字按归位（即将数字 i 放在下标为 i 的位置），若同一个位置上存在多个数字，则找到重复数字。

*/

class Solution {

/**

* 时间复杂度：O(n * logn)

* 空间复杂度：O(1)

*/

public int findRepeatNumber1(int[] nums) {

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

return -1;

}

// sort array, make same elements to adjacent.

Arrays.sort(nums);

// traverse array to judge two adjacent elements is same or not.

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

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

return nums[i];

}

}

// none of duplication.

return -1;

}

/**

* 时间复杂度：O(n)

* 空间复杂度：O(n)

*/

public int findRepeatNumber2(int[] nums) {

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

return -1;

}

// use array to storage number had appeared or not.

boolean[] appeared = new boolean[nums.length];

// traverse array nums.

for (int num : nums) {

// if current number had appeared, find the duplication.

if (appeared[num]) {

return num;

}

// use array appeared mark number had appeared.

appeared[num] = true;

}

// none of duplication.

return -1;

}

/**

* 时间复杂度: O(n)

* 空间复杂度: O(1)

*/

public int findRepeatNumber3(int[] nums) {

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

return -1;

}

// traverse array nums.

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

// if current number isn't in it's right position,

// judge right position's element is same of its or not.

// if same, find the duplication;

// if not, swap its and the right position element,

// then continue while process(judge current element is in it's right position or not).

while (i != nums[i]) {

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

return nums[i];

} else {

swap(nums, i, nums[i]);

}

}

}

// none of duplication.

return -1;

}

private void swap(int[] arr, int a, int b) {

int temp = arr[b];

arr[b] = arr[a];

arr[a] = temp;

}

}