diff options
| -rwxr-xr-x | 540/main.py | 39 |
1 files changed, 39 insertions, 0 deletions
diff --git a/540/main.py b/540/main.py new file mode 100755 index 0000000..29cc1d3 --- /dev/null +++ b/540/main.py @@ -0,0 +1,39 @@ +#!/usr/bin/env python +from typing import List + + +class Solution: + def singleNonDuplicate(self, nums: List[int]) -> int: + start = 0 + end = len(nums) - 1 + mid = 0 + + if len(nums) == 1: + return nums[0] + + while start < end: + mid = (start + end) // 2 + if nums[mid] == nums[mid + 1]: + if (end - mid + 1) % 2 == 0: + end = mid - 1 + else: + start = mid + elif nums[mid] == nums[mid - 1]: + if (mid - start + 1) % 2 == 0: + start = mid + 1 + else: + end = mid + else: + return nums[mid] + + return nums[end] + + +if __name__ == "__main__": + solution = Solution() + assert solution.singleNonDuplicate([1, 1, 2, 3, 3, 4, 4, 8, 8]) == 2 + assert solution.singleNonDuplicate([3, 3, 7, 7, 10, 11, 11]) == 10 + assert solution.singleNonDuplicate([1, 2, 2, 3, 3, 4, 4, 8, 8]) == 1 + assert solution.singleNonDuplicate([1, 1, 2, 2, 3, 3, 4, 4, 8]) == 8 + assert solution.singleNonDuplicate([1, 1, 2]) == 2 + assert solution.singleNonDuplicate([0, 1, 1, 2, 2, 5, 5]) == 0 |