Single Element in a Sorted Array
sorted肯定是让二分了, 但是这个二分需要判断奇偶, 所以先发个不二分的.
|
1 2 3 4 5 6 7 8 9 |
class Solution { public int singleNonDuplicate(int[] nums) { int n = nums[0]; for(int i = 1; i < nums.length; i++) { n ^= nums[i]; // xor remove all twice numbers } return n; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public int singleNonDuplicate(int[] nums) { int lo = 0; int hi = nums.length - 1; while(lo < hi) { int mid = lo + (hi - lo) / 2; if(mid % 2 != 0) // if it is not a even number, make it even number mid += 1; if(nums[mid] == nums[mid-1]) hi = mid - 2; else lo = mid; } return nums[lo]; } } |