From 6dc6d6a2b5c1a4fc5cef56b74f43730955d8dd54 Mon Sep 17 00:00:00 2001 From: terminaldweller Date: Tue, 21 Feb 2023 09:18:01 +0330 Subject: 540 --- 540/main.py | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) create mode 100755 540/main.py (limited to '540/main.py') 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 -- cgit v1.2.3