给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]输出: 1
示例 2:
输入: [4,1,2,1,2]输出: 4
以上是原题
OK,先找出题目中的重点要求:
1、线性时间复杂度:要求我们的代码时间复杂度最高为O(n),不能有嵌套循环等。
2、不使用额外空间:要求空间复杂度最高为O(1)。
除此之外,还有重要的信息:
- 除了某个元素只出现一次以外,其余每个元素均出现两次。
这个条件非常关键,一开始自己审题不清楚没注意到均出现两次这个关键点,按照其他元素出现多次的情况处理了,这样导致思路受限很多。
开始解题:
方法一(比较法):
思路:先对数组进行排序,然后对 nums[i] 和 nums[i + 1]进行比较,如相等,i += 2,继续下一组比较,直到取到不相等的一组。
注意:首先这个数组的长度肯定是奇数(目标数字只出现一次,其他所有数字出现两次),所以如果上述步骤没有找到不相等的一组数,那么肯定是数组的最后一个数字是单独出现的。
代码如下:
1 public static int singleNumber(int[] nums) { 2 Arrays.sort(nums); // 排序数组 3 for (int i = 0; i < nums.length - 1; i += 2) { 4 // 找到不相等的一组,直接返回 5 if (nums[i] != nums[i + 1]) { 6 return nums[i]; 7 } 8 } 9 // 如果没有找到不相等的一组数据,直接返回数组的最后一个数字10 return nums[nums.length - 1];11 }
方法二(去重法):
思路:利用HashSet的特性,删除重复的数组元素,最后剩下一个单独的元素,返回即可。
直接上代码:
1 public static int singleNumber(int[] nums) {2 Setset = new HashSet<>();3 for (int i = 0; i < nums.length; i++) {4 if (!set.add(nums[i])) { // add成功返回true,如果set中已有相同数字,则add方法会返回false5 set.remove(nums[i]); // 删除重复出现的数字6 }7 }8 return set.iterator().next();9 }
方法三(求差法):
思路:先对数组排序,显而易见的,单独出现一次的数据必然是出现在数组下标为偶数的位置(下标从0开始),那么所有奇数下标的元素之和减去偶数下标的元素之和,就是需要求得的结果。
代码如下:
1 public static int singleNumber(int[] nums) {2 int num = 0;3 Arrays.sort(nums);4 for (int i = 0; i < nums.length; i++) {5 // 偶数下标位置 num += nums[i],奇数下标位置 num -= nums[i]6 num = i % 2 == 0 ? num + nums[i] : num - nums[i];7 }8 return num;9 }
方法四(异或法):
思路:根据异或运算的特点,相同的数字经过异或运算后结果为0,除单独出现一次的数字外,其他数字都是出现两次的,那么这些数字经过异或运算后结果一定是0。而任何数字与0进行异或运算都是该数字本身。所以对数组所有元素进行异或运算,运算结果就是题目的答案。
上代码:
1 public static int singleNumber(int[] nums) {2 int num = 0;3 for (int i = 0; i < nums.length; i++) {4 num = num ^ nums[i];5 }6 return num;7 }
总结:
其实严格来讲,只有第四种方式是题目想要的解法,其他三种方法都是有瑕疵的。
方法一、方法三都用到了Arrays.sort(int[] a)的方法,我们先来看JDK提供的数组排序方法:
1 public static void sort(int[] a) {2 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);3 }
调用了DualPivotQuicksort类的静态方法:
1 /** 2 * Sorts the specified range of the array using the given 3 * workspace array slice if possible for merging 4 * 5 * @param a the array to be sorted 6 * @param left the index of the first element, inclusive, to be sorted 7 * @param right the index of the last element, inclusive, to be sorted 8 * @param work a workspace array (slice) 9 * @param workBase origin of usable space in work array 10 * @param workLen usable size of work array 11 */ 12 static void sort(int[] a, int left, int right, 13 int[] work, int workBase, int workLen) { 14 // Use Quicksort on small arrays 15 if (right - left < QUICKSORT_THRESHOLD) { 16 sort(a, left, right, true); 17 return; 18 } 19 20 /* 21 * Index run[i] is the start of i-th run 22 * (ascending or descending sequence). 23 */ 24 int[] run = new int[MAX_RUN_COUNT + 1]; 25 int count = 0; run[0] = left; 26 27 // Check if the array is nearly sorted 28 for (int k = left; k < right; run[count] = k) { 29 if (a[k] < a[k + 1]) { // ascending 30 while (++k <= right && a[k - 1] <= a[k]); 31 } else if (a[k] > a[k + 1]) { // descending 32 while (++k <= right && a[k - 1] >= a[k]); 33 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) { 34 int t = a[lo]; a[lo] = a[hi]; a[hi] = t; 35 } 36 } else { // equal 37 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) { 38 if (--m == 0) { 39 sort(a, left, right, true); 40 return; 41 } 42 } 43 } 44 45 /* 46 * The array is not highly structured, 47 * use Quicksort instead of merge sort. 48 */ 49 if (++count == MAX_RUN_COUNT) { 50 sort(a, left, right, true); 51 return; 52 } 53 } 54 55 // Check special cases 56 // Implementation note: variable "right" is increased by 1. 57 if (run[count] == right++) { // The last run contains one element 58 run[++count] = right; 59 } else if (count == 1) { // The array is already sorted 60 return; 61 } 62 63 // Determine alternation base for merge 64 byte odd = 0; 65 for (int n = 1; (n <<= 1) < count; odd ^= 1); 66 67 // Use or create temporary array b for merging 68 int[] b; // temp array; alternates with a 69 int ao, bo; // array offsets from 'left' 70 int blen = right - left; // space needed for b 71 if (work == null || workLen < blen || workBase + blen > work.length) { 72 work = new int[blen]; 73 workBase = 0; 74 } 75 if (odd == 0) { 76 System.arraycopy(a, left, work, workBase, blen); 77 b = a; 78 bo = 0; 79 a = work; 80 ao = workBase - left; 81 } else { 82 b = work; 83 ao = 0; 84 bo = workBase - left; 85 } 86 87 // Merging 88 for (int last; count > 1; count = last) { 89 for (int k = (last = 0) + 2; k <= count; k += 2) { 90 int hi = run[k], mi = run[k - 1]; 91 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { 92 if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) { 93 b[i + bo] = a[p++ + ao]; 94 } else { 95 b[i + bo] = a[q++ + ao]; 96 } 97 } 98 run[++last] = hi; 99 }100 if ((count & 1) != 0) {101 for (int i = right, lo = run[count - 1]; --i >= lo;102 b[i + bo] = a[i + ao]103 );104 run[++last] = right;105 }106 int[] t = a; a = b; b = t;107 int o = ao; ao = bo; bo = o;108 }109 }
代码较长,想看的同学点开看一下,可以发现这个方法的时间复杂度是O(n3),不符合题目的要求线性时间复杂度。
方法二呢,是利用了HashSet集合不可重复的特性,同样我们来看HashSet的add方法:
1 /** 2 * Adds the specified element to this set if it is not already present. 3 * More formally, adds the specified element e to this set if 4 * this set contains no element e2 such that 5 * (e==null ? e2==null : e.equals(e2)). 6 * If this set already contains the element, the call leaves the set 7 * unchanged and returns false. 8 * 9 * @param e element to be added to this set10 * @return true if this set did not already contain the specified11 * element12 */13 public boolean add(E e) {14 return map.put(e, PRESENT)==null;15 }
其实HashSet的底层是通过HashMap来实现的,HashSet中的元素都是HashMap中的key,再来看HashMap的put方法:
1 /** 2 * Associates the specified value with the specified key in this map. 3 * If the map previously contained a mapping for the key, the old 4 * value is replaced. 5 * 6 * @param key key with which the specified value is to be associated 7 * @param value value to be associated with the specified key 8 * @return the previous value associated with key, or 9 * null if there was no mapping for key.10 * (A null return can also indicate that the map11 * previously associated null with key.)12 */13 public V put(K key, V value) {14 return putVal(hash(key), key, value, false, true);15 }16 17 /**18 * Implements Map.put and related methods19 *20 * @param hash hash for key21 * @param key the key22 * @param value the value to put23 * @param onlyIfAbsent if true, don't change existing value24 * @param evict if false, the table is in creation mode.25 * @return previous value, or null if none26 */27 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,28 boolean evict) {29 Node[] tab; Node p; int n, i;30 if ((tab = table) == null || (n = tab.length) == 0)31 n = (tab = resize()).length;32 if ((p = tab[i = (n - 1) & hash]) == null)33 tab[i] = newNode(hash, key, value, null);34 else {35 Node e; K k;36 if (p.hash == hash &&37 ((k = p.key) == key || (key != null && key.equals(k))))38 e = p;39 else if (p instanceof TreeNode)40 e = ((TreeNode )p).putTreeVal(this, tab, hash, key, value);41 else {42 for (int binCount = 0; ; ++binCount) {43 if ((e = p.next) == null) {44 p.next = newNode(hash, key, value, null);45 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st46 treeifyBin(tab, hash);47 break;48 }49 if (e.hash == hash &&50 ((k = e.key) == key || (key != null && key.equals(k))))51 break;52 p = e;53 }54 }55 if (e != null) { // existing mapping for key56 V oldValue = e.value;57 if (!onlyIfAbsent || oldValue == null)58 e.value = value;59 afterNodeAccess(e);60 return oldValue;61 }62 }63 ++modCount;64 if (++size > threshold)65 resize();66 afterNodeInsertion(evict);67 return null;68 }
请注意:上面 putVal 方法中,调用的 resize() 、 putTreeVal() 等方法本身也是O(n2)的时间复杂度。不符合题目要求的线性时间复杂度。
所以严格来说,只有第四种方式符合题目要求,但我们拓宽思路,能多用几种还算不错的方式实现需求,也是有百利而无一害的,大家也不必非要钻这个牛角尖。
另外,从效率上来讲,第四种效率是最高的,经过测试高出前三种方式1-2个数量级。只是在普通的业务代码中,用到异或运算的地方并不多,不太容易想到这种方式,这个就考验大家的基础功底了。