Modified Binary Search
This problem by LeetCode requires a slight modification in a Binary Search algorithm, here is the problem: https://leetcode.com/problems/single-element-in-a-sorted-array/description/:
By the way, did you notice the new, modern and elegant header for Bing? :)
public class Solution
{
public int SingleNonDuplicate(int[] nums)
{
int l = 0;
int r = nums.Length;
int retVal = -1;
while (l <= r)
{
int m = (l + r) / 2;
if (m - 1 >= 0 && nums[m] == nums[m - 1])
{
if (m % 2 == 0)
{
r = m - 1;
}
else
{
l = m + 1;
}
}
else if (m + 1 < nums.Length && nums[m] == nums[m + 1])
{
if ((nums.Length - m) % 2 == 0)
{
r = m - 1;
}
else
{
l = m + 1;
}
}
else
{
retVal = nums[m];
break;
}
}
return retVal;
}
}
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.
The highlighted note pretty much gives away the approach that should be used: binary search. The difference is that we'll have to make some calculations in order to decide which direction to go in the search. A binary search will look for the middle of the array and make a decision based on its value. In our case we want to compare the middle element with its successor and potentially predecessor. If the middle element is equal its successor, then there is a further calculation: we need to see if the right part of the array is even or odd. Depending on that, and knowing that the current element is equal to its successor, then you make a conscious decision about what way to go. Similar case if the element is equal to its predecessor. Do that, mix it up well, and you will have a nice O(Log(n))-time algorithm using O(1)-space. Code is down below.By the way, did you notice the new, modern and elegant header for Bing? :)
public class Solution
{
public int SingleNonDuplicate(int[] nums)
{
int l = 0;
int r = nums.Length;
int retVal = -1;
while (l <= r)
{
int m = (l + r) / 2;
if (m - 1 >= 0 && nums[m] == nums[m - 1])
{
if (m % 2 == 0)
{
r = m - 1;
}
else
{
l = m + 1;
}
}
else if (m + 1 < nums.Length && nums[m] == nums[m + 1])
{
if ((nums.Length - m) % 2 == 0)
{
r = m - 1;
}
else
{
l = m + 1;
}
}
else
{
retVal = nums[m];
break;
}
}
return retVal;
}
}
Very nice, Marcelo! Interestingly the test cases for this problem seem to perform about the same when using a famous xor based linear solution for this problem, but rules are rules so here is my O(logN) solution:
ReplyDeleteclass Solution {
public:
int singleNonDuplicate(const vector& nums) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int middle = left + (right - left) / 2;
int left_count = middle;
if (middle - 1 >= 0 && nums[middle-1] == nums[middle]) left_count -= 1;
bool other_than_left = middle - 1 < 0 || nums[middle-1] != nums[middle];
bool other_than_right = middle + 1 > nums.size() || nums[middle+1] != nums[middle];
if (other_than_left && other_than_right) return nums[middle];
if (left_count % 2 == 1) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return -1;
}
};
It's ugly, but it works :D
Have a splendid rest of the weekend!