只出现一次的数字 问题描述 给定一个非空整数数组, 除了某个元素只出现一次以外, 其余每个元素均出现两次. 找出那个只出现了一次的元素.
题目地址: https://leetcode-cn.com/problems/single-number/
说明 你的算法应该具有线性时间复杂度. 你可以不使用额外空间来实现吗？
示例 输入: [2,2,1] 输出: 1 输入: [4,1,2,1,2] 输出: 4 解答 开始想的是用collection函数来统计次数, 但发现题目的说明讲到了不使用额外的空间, 所以作罢.
后来想用sort来进行排序, 再进行for num in nums进行遍历, 来判断相邻两个是否相同从而找出不同的元素, 但这样O(n)的时间复杂度就太高了. 而且严格来说sort也使用了额外的空间(见下文解释)
python的sort方法 见python源码中的sort实现
int PyList_Sort(PyObject *v) { if (v == NULL || !PyList_Check(v)) { PyErr_BadInternalCall(); return -1; } v = list_sort_impl((PyListObject *)v, NULL, 0); if (v == NULL) return -1; Py_DECREF(v); return 0; } 使用的是Timsort算法, 从时间复杂度来讲, 这个算法是高效的.
从空间复杂度来讲，需要的开销在数量大的时候会增大.
下面是JSE7 中Timsort实现代码中的一段话，可以很好的说明Timsort的优势：
A stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays. Like all proper mergesorts, this sort is stable and runs O(n log n) time (worst case). In the worst case, this sort requires temporary storage space for n/2 object references; in the best case, it requires only a small constant amount of space.
...