Welcome to Subscribe On Youtube
-
/** 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 Single_Element_in_a_Sorted_Array { class Solution { public int singleNonDuplicate(int[] nums) { if (nums == null || nums.length == 0) { return -1; } 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]; } } } ############ class Solution { public int singleNonDuplicate(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = (left + right) >> 1; // if ((mid % 2 == 0 && nums[mid] != nums[mid + 1]) || (mid % 2 == 1 && nums[mid] != // nums[mid - 1])) { if (nums[mid] != nums[mid ^ 1]) { right = mid; } else { left = mid + 1; } } return nums[left]; } }
-
// OJ: https://leetcode.com/problems/single-element-in-a-sorted-array/ // Time: O(logN) // Space: O(1) class Solution { public: int singleNonDuplicate(vector<int>& A) { int L = 0, R = A.size() - 1; while (L < R) { int M = (L + R) / 2; if ((M % 2 == 0 && A[M] == A[M + 1]) || (M % 2 == 1 && A[M] == A[M - 1])) L = M + 1; else R = M; } return A[L]; } };
-
class Solution: def singleNonDuplicate(self, nums: List[int]) -> int: left, right = 0, len(nums) - 1 while left < right: mid = (left + right) >> 1 # Equals to: if (mid % 2 == 0 and nums[mid] != nums[mid + 1]) or (mid % 2 == 1 and nums[mid] != nums[mid - 1]): if nums[mid] != nums[mid ^ 1]: right = mid else: left = mid + 1 return nums[left] ############ class Solution(object): def singleNonDuplicate(self, nums): """ :type nums: List[int] :rtype: int """ return reduce(lambda x, y: x^y, nums)
-
func singleNonDuplicate(nums []int) int { left, right := 0, len(nums)-1 for left < right { mid := (left + right) >> 1 if nums[mid] != nums[mid^1] { right = mid } else { left = mid + 1 } } return nums[left] }
-
function singleNonDuplicate(nums: number[]): number { let left = 0, right = nums.length - 1; while (left < right) { const mid = (left + right) >> 1; if (nums[mid] != nums[mid ^ 1]) { right = mid; } else { left = mid + 1; } } return nums[left]; }
-
impl Solution { pub fn single_non_duplicate(nums: Vec<i32>) -> i32 { let mut l = 0; let mut r = nums.len() - 1; while l < r { let mid = l + r >> 1; if nums[mid] == nums[mid ^ 1] { l = mid + 1; } else { r = mid; } } nums[l] } }
-
class Solution { public int singleNonDuplicate(int[] nums) { int low = 0, high = nums.length - 1; while (low < high) { if (high - low == 1) { if (low == 0) return nums[low]; else if (high == nums.length - 1) return nums[high]; } int mid = (high - low) / 2 + low; int num = nums[mid]; if (num != nums[mid - 1] && num != nums[mid + 1]) return num; else { if (mid % 2 == 0 && num == nums[mid + 1] || mid % 2 == 1 && num == nums[mid - 1]) low = mid + 1; else high = mid - 1; } } return nums[low]; } } ############ class Solution { public int singleNonDuplicate(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = (left + right) >> 1; // if ((mid % 2 == 0 && nums[mid] != nums[mid + 1]) || (mid % 2 == 1 && nums[mid] != // nums[mid - 1])) { if (nums[mid] != nums[mid ^ 1]) { right = mid; } else { left = mid + 1; } } return nums[left]; } }
-
// OJ: https://leetcode.com/problems/single-element-in-a-sorted-array/ // Time: O(logN) // Space: O(1) class Solution { public: int singleNonDuplicate(vector<int>& A) { int L = 0, R = A.size() - 1; while (L < R) { int M = (L + R) / 2; if ((M % 2 == 0 && A[M] == A[M + 1]) || (M % 2 == 1 && A[M] == A[M - 1])) L = M + 1; else R = M; } return A[L]; } };
-
class Solution: def singleNonDuplicate(self, nums: List[int]) -> int: left, right = 0, len(nums) - 1 while left < right: mid = (left + right) >> 1 # Equals to: if (mid % 2 == 0 and nums[mid] != nums[mid + 1]) or (mid % 2 == 1 and nums[mid] != nums[mid - 1]): if nums[mid] != nums[mid ^ 1]: right = mid else: left = mid + 1 return nums[left] ############ class Solution(object): def singleNonDuplicate(self, nums): """ :type nums: List[int] :rtype: int """ return reduce(lambda x, y: x^y, nums)
-
func singleNonDuplicate(nums []int) int { left, right := 0, len(nums)-1 for left < right { mid := (left + right) >> 1 if nums[mid] != nums[mid^1] { right = mid } else { left = mid + 1 } } return nums[left] }
-
function singleNonDuplicate(nums: number[]): number { let left = 0, right = nums.length - 1; while (left < right) { const mid = (left + right) >> 1; if (nums[mid] != nums[mid ^ 1]) { right = mid; } else { left = mid + 1; } } return nums[left]; }
-
impl Solution { pub fn single_non_duplicate(nums: Vec<i32>) -> i32 { let mut l = 0; let mut r = nums.len() - 1; while l < r { let mid = l + r >> 1; if nums[mid] == nums[mid ^ 1] { l = mid + 1; } else { r = mid; } } nums[l] } }