Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
Example 1:
Input: nums = [2,2,1] Output: 1
Example 2:
Input: nums = [4,1,2,1,2] Output: 4
Example 3:
Input: nums = [1] Output: 1
Constraints:
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- Each element in the array appears twice except for one element which appears only once.
Your algorithm should run in O(n log n) time and use O(1) extra space (when the array is sorted in place).
(There are faster solutions which we will discuss in future lessons)
Hints:
Let's sort the array in non-decreasing order. In this way all the equal elements will come one after another.
Let's take an example: if
nums is [2,1,3,1,3], sorting it gives [1,1,2,3,3].The single element is 2. What property does it satisfy that the other elements don't?
After sorting the array, the single element is the only one that is different than both its neighbors.
More exactly, in sorted
nums, the element at index i is the single element if both these conditions hold true:iis the first index, or the previous element is different from the element at indexiiis the last index, or the next element is different from the element at indexi
We sort the array, thus the Time Complexity is
O(n log n).If we sort
nums in place, we don't use any extra arrays, so the Extra Space used is O(1). (Sorting a copy, as Swift's sorted() does, would take O(n) extra space.)
Walkthroughs of the solution. Try the steps first, then watch to compare approaches.
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
