Difficulty: Medium Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
language c
/** * Return an array of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */ int* singleNumber(int* a, int numsSize, int* returnSize) { void sort(int * a, int left, int right); sort(a, 0, numsSize-1); int* returntp = (int *)malloc(2*sizeof(int)); int i; int count = 0; *returnSize = 2; if (a[0] != a[1]) { returntp[0] = a[0]; count++; } for (i = 1; i < numsSize - 1; i++) { if (a[i] != a[i-1] && a[i] != a[i+1]) { if (count == 1) { returntp[count] = a[i]; return returntp; } else { returntp[count] = a[i]; count++; } } } returntp[count] = a[i]; return returntp; } void swap(int *one, int *two) { int temp = *one; *one = *two; *two = temp; } void sort(int * a, int left, int right) { int i = left, j = right; if (left >= right) return; int pivot = a[(left+right)/2]; swap(&a[left], &a[(left+right)/2]); pivot = a[left]; while(left < right) { while(left < right && pivot <= a[right]) right--; a[left] = a[right]; while (left < right && pivot >= a[left]) left++; a[right] = a[left]; } a[left] = pivot; sort(a, i, left-1); sort(a,left+1, j); }先用快排排一次序，然后两两比较。 快排如果选择一个基准（如去数列中间位置的为基准），可以提速很多
