class Solution {
public:
int singleNonDuplicate(vector <int> &nums);
};
|
Here are the details of the problem:
UNIX> echo 1 1 2 3 3 4 4 8 8 | ./a.out # This is their example 1 2 UNIX> echo 3 3 7 7 10 11 11 | ./a.out # This is their example 2 10 UNIX> echo 1 | ./a.out 1 UNIX> echo 1 2 2 | ./a.out 1 UNIX> echo 1 1 2 | ./a.out 2 UNIX>There are 100 example input problems in this directory (which you can get from our EECS machines if you are at the University of Tennessee. Otherwise, you can get them from the files.tgz file linked above). They range in size from very small to hitting the constraints. For example:
UNIX> cat input-06.txt
64968
64968
73717
UNIX> ./a.out < input-06.txt
73717
UNIX> cat input-12.txt
40306
40306
45989
92737
92737
UNIX> a.out < input-12.txt
45989
UNIX> wc input-50.txt
15 15 88 input-50.txt
UNIX> ./a.out < input-50.txt
77725
UNIX> grep 77725 input-50.txt # This confirms that 77725 appears exactly once in the file.
77725
UNIX> wc input-90.txt
19999 19999 117756 input-90.txt
UNIX> ./a.out < input-90.txt
18114
UNIX> grep 18114 input-90.txt # This confirms that 18114 appears exactly once in the file.
18114
UNIX>
It won't be faster if you measure it properly. The problem with the leetcode test (and with my inputs for that matter) is that generating the problem is O(n), so it may be hard to measure the runtime of the solution. If you properly measure the solution time rather than the problem generation time, you can easily show that O(log n) outperforms O(n). It's a pity the leetcode tests didn't do this.
That comment is one of those comments that won't get you hired for two reasons. First, it shows that you don't understand the value of an O(log n) solution as compared to an O(n) solution. I would pass on hiring you for that. Second, writing "O(N/2)" shows that you don't understand big-O, and I would definitely pass on hiring you for that.
If you agree with the comment above, you are missing the point, so please take some time to understand why O(log n) is vastly superior to O(n), even if the leetcode problem doesn't test it properly.
The binary search actually doesn't require the numbers to be sorted. It simply requires the pairs to be together. What you do is roughly the following
|--------------------------|------|-------------------------|
nums: | elements-before-the-pair | pair | elements-after-the-pair |
|--------------------------|------|-------------------------|
If this is odd, then the If this is odd, then the
single element is in here single element is in here
|
Now, the concept there is straightforward. How to implement it? I maintained a while loop with four variables:
Let's do some examples:
UNIX> cat input-06.txt 64968 64968 73717 # Here's the unique value UNIX> ./a.out < input-06.txt low = 0. high = 2. high - low <= 2 - calculate the answer. 73717 UNIX> cat input-12.txt 40306 40306 45989 # Here's the unique value 92737 92737 UNIX> ./a.out < input-12.txt low = 0. high = 4. mid = 2. nums[mid] = 45989. Not part of a pair, return. 45989 UNIX> cat input-13.txt 28868 28868 31958 # Here's the unique value 97310 97310 UNIX> cat input-14.txt 37299 # Here's the unique value 68537 68537 89939 89939 UNIX> ./a.out < input-14.txt low = 0. high = 4. mid = 2. nums[mid] = 68537. pli: 1. low = 0. high = 0. high - low <= 2 - calculate the answer. 37299 UNIX> cat input-50.txt 2268 2268 20560 20560 41719 41719 55466 55466 65085 65085 66067 66067 77725 # Here's the unique value 89233 89233 UNIX> ./a.out < input-50.txt low = 0. high = 14. mid = 7. nums[mid] = 55466. pli: 6. low = 8. high = 14. mid = 11. nums[mid] = 66067. pli: 10. low = 12. high = 14. high - low <= 2 - calculate the answer. 77725 UNIX> cat input-47.txt 10649 10649 12866 # Here's the unique value 15839 15839 23952 23952 41625 41625 52714 52714 73624 73624 91269 91269 UNIX> ./a.out < input-47.txt low = 0. high = 14. mid = 7. nums[mid] = 41625. pli: 7. low = 0. high = 6. mid = 3. nums[mid] = 15839. pli: 3. low = 0. high = 2. high - low <= 2 - calculate the answer. 12866 UNIX>