FilesExpand file tree

 master

/

SingleElementInASortedArray540.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

112 lines (93 loc) · 3.47 KB

 master

/

SingleElementInASortedArray540.java

Copy path

Top

File metadata and controls

• Code
• Blame

112 lines (93 loc) · 3.47 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

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

/**

* Given a sorted array consisting of only integers where every element appears

* twice except for one element which appears once. Find this single element

* that appears only once.

*

* Example 1:

* Input: [1,1,2,3,3,4,4,8,8]

* Output: 2

*

* Example 2:

* Input: [3,3,7,7,10,11,11]

* Output: 10

*

* Note: Your solution should run in O(log n) time and O(1) space.

*/

public class SingleElementInASortedArray540 {

public int singleNonDuplicate(int[] nums) {

if (nums.length == 1) return nums[0];

return singleNonDuplicate(nums, 0, nums.length-1);

}

private int singleNonDuplicate(int[] nums, int lo, int hi) {

if (lo == hi) return nums[lo];

int mid = (lo + hi) / 2;

boolean b = (mid - lo) % 2 == 0;

if (nums[mid] != nums[mid-1] && nums[mid] != nums[mid+1]) {

return nums[mid];

}

if (nums[mid] != nums[mid-1]) {

if (b) {

return singleNonDuplicate(nums, mid, hi);

} else {

return singleNonDuplicate(nums, lo, mid-1);

}

}

if (b) {

return singleNonDuplicate(nums, lo, mid);

} else {

return singleNonDuplicate(nums, mid+1, hi);

}

}

private int singleNonDuplicate2(int[] nums, int lo, int hi) {

if (lo == hi) return nums[lo];

int mid = (lo + hi) / 2;

boolean b = (mid - lo) % 2 == 0;

if (nums[mid] != nums[mid-1] && nums[mid] != nums[mid+1]) {

return nums[mid];

}

if ((nums[mid] == nums[mid-1]) == b) {

if (nums[mid] != nums[mid-1]) mid--;

return singleNonDuplicate2(nums, lo, mid);

}

if (nums[mid] == nums[mid-1]) mid++;

return singleNonDuplicate2(nums, mid, hi);

}

private int singleNonDuplicate3(int[] nums, int lo, int hi) {

if (lo == hi) return nums[lo];

int mid = (lo + hi) / 2;

if (nums[mid] != nums[mid-1] && nums[mid] != nums[mid+1]) return nums[mid];

if (mid % 2 == 1) mid--;

if (nums[mid] != nums[mid+1]) return singleNonDuplicate3(nums, lo, mid);

return singleNonDuplicate3(nums, mid+2, hi);

}

/**

* https://leetcode.com/problems/single-element-in-a-sorted-array/discuss/100754/Java-Binary-Search-short-(7l)-O(log(n))-w-explanations

*/

public static int singleNonDuplicate2(int[] nums) {

int start = 0, end = nums.length - 1;

while (start < end) {

// We want the first element of the middle pair,

// which should be at an even index if the left part is sorted.

// Example:

// Index: 0 1 2 3 4 5 6

// Array: 1 1 3 3 4 8 8

// ^

int mid = (start + end) / 2;

if (mid % 2 == 1) mid--;

// We didn't find a pair. The single element must be on the left.

// (pipes mean start & end)

// Example: |0 1 1 3 3 6 6|

// ^ ^

// Next: |0 1 1|3 3 6 6

if (nums[mid] != nums[mid + 1]) end = mid;

// We found a pair. The single element must be on the right.

// Example: |1 1 3 3 5 6 6|

// ^ ^

// Next: 1 1 3 3|5 6 6|

else start = mid + 2;

}

// 'start' should always be at the beginning of a pair.

// When 'start > end', start must be the single element.

return nums[start];

}

}