一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

107 阅读 0 评论 71 点赞

我是靠谱客的博主可耐棒棒糖，这篇文章主要介绍一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。，现在分享给大家，希望可以做个参考。

1.一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

2.代码展示

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int _QuickSort(int *nums, int left, int right)
{
int key = nums[right];
int index = right;
while (left < right)
{
while (left < right)
{
if (nums[left] > key)
{
nums[index] = nums[left];
index = left;
break;
}
++left;
}
while (left < right)
{
if (nums[right] < key)
{
nums[index] = nums[right];
index = right;
break;
}
--right;
}
}
nums[left] = key;
return left;
}
void
QuickSort(int *nums, int left, int right)
{
if (left > right)
{
return;
}
int index = _QuickSort(nums, left, right);
QuickSort(nums, left, index - 1);
QuickSort(nums, index + 1, right);
}
//快排
//双指针
int* singleNumbers(int* nums, int numsSize, int* returnSize) {
*returnSize = 0;
QuickSort(nums, 0, numsSize - 1);
for (int i = 0; i < numsSize; i++)
{
if (i+1<numsSize && nums[i] == nums[i + 1])
{
i = i + 1;
}
else
{
nums[(*returnSize)++] = nums[i];
}
}
return nums;
}