Leetcode-136.只出现一次的数字
题目：给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，
其余每个元素均出现两次。找出那个只出现了一次的元素。
我们的思路是，把数组中的数全部异或在一起，相同的数异或在一起等于0，而0和任意数异或等于任意数；
int singleNumber(int* nums, int numsSize) { int single = 0; for (int i = 0; i < numsSize; i++) { single ^= nums[i]; } return single; }
Leetcode-169.多数元素
题目：给定一个大小为 n 的数组 nums ，返回其中的多数元素。
多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素
1.直接排序暴力求解法1
这个思路是，直接将数组快排，然后用count统计当前的元素是否满足条件，若满足，返回；若不满足，更新当前的元素，继续用count统计；直到最后一个元素都没返回的话，那么最后一个元素就是多数元素，因为可以假设给定的数组总是存在多数元素，所以上面没有返回的话，肯定是最后一项就是多数元素；
int compare(const void* p1, const void* p2) { return (*(int*)p1 - *(int*)p2); } int majorityElement(int* nums, int numsSize) { int count = 0, i = 0; //排序数组，从小到大 qsort(nums, numsSize, sizeof(int), compare); //初始化flag的值为排序好的数组第一项 int flag = nums[0]; //从头开始遍历 for (i = 0; i < numsSize; i++) { //如果这一项与flag当前的项相等，count++ if (flag == nums[i]) { count++; } //如果不相等，将这一项赋给flag，更新当前的flag //并计算当前的count是否已经大于 numsSize / 2，如果大于，直接返回 //如果还没有大于，将count置0，继续寻找，并且++，因为是i++后再进来的else，没有统计当前这个flag else { flag = nums[i]; if (count > numsSize / 2) { return nums[i - 1]; } count = 0; count++; } } //因为可以假设给定的数组总是存在多数元素 //所以上面没有返回的话，肯定是最后一项就是多数元素 return nums[i - 1]; }
2. 直接排序暴力求解法2
因为多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素，所以排序后，下标为 numsSize / 2 的一定为多数元素；
int compare(const void* p1, const void* p2) { return (*(int*)p1 - *(int*)p2); } int majorityElement(int* nums, int numsSize) { //排序数组，从小到大 qsort(nums, numsSize, sizeof(int), compare); return nums[numsSize / 2]; }
3. 投票法
还有一个思路是投票法，将不同的元素相互抵消，存留到最后的一定就是多数元素；
int majorityElement(int* nums, int numsSize) { int majority = nums[0], count = 0; for (int i = 0; i < numsSize; i++) { //遍历数组，如果nums[i]等于需要投票的数字，count++ if (majority == nums[i]) { count++; } //如果不等于，count-- //并判断count是否小于0，若小于0，更新majority，并改count为1 //注意，count小于0也不能说明当前的num[i]或者majority是多数元素 //只能说明num[i]之前不同的元素已经完全抵消，从nums[i]开始往后继续抵消 else { count--; if (count < 0) { majority = nums[i]; count = 1; } } } return majority; }
