怎样建设电影网站,建设工程施工合同的特征,怎么访问wordpress,深圳 网站建设设计消失的数字 解法一#xff1a;求和相减
假设nums为[0,1,2,4],消失的数字为3#xff0c;完整的数组应该是[0,1,2,3,4]#xff0c;则sum101247,sum20123410#xff0c;我们很容易发现 sum2-sum1 01234 - 0124 3#xff0c;即为消失的数字。因此#xff0c;我们可以采用先…消失的数字 解法一求和相减
假设nums为[0,1,2,4],消失的数字为3完整的数组应该是[0,1,2,3,4]则sum101247,sum20123410我们很容易发现 sum2-sum1 01234 - 0124 3即为消失的数字。因此我们可以采用先相加再相减的方法就可以求出消失的数字。 代码如下
int missingNumber(int* nums, int numsSize)
{int tmp 0;int talg 0;for (int i 0;i numsSize;i){tmp tmp i;//求数组下标之和}for (int j 0;j numsSize;j){talg nums[j];//求数组元素之和}return tmp - talg;
}解法二异或
首先我们得清楚异或 ^ 的原理 相同为0相异为1并且0^任何数都等它本身 a ^ a 0、a ^ b b ^ a、0 ^ a a 、(a!b) 那么根据上述的原理我们便可以使用异或进行解题 首先异或上所有数n即为此数组元素个数即ret 0 ^ 1^ 2^ …^n 然后对数组元素异或nums[0]^ nums[1] ^ …^ nums[numsSize-1] 然后异或这二者即 ret 0^ 1^ 2^ 3^ …^ n^ nums[0] ^ nums[1]^ …^nums[numsSize-1] 最终ret就为消失的数字 打个比方nums[] {2,3,4,5,6} ret 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 1.
int missingNumber(int* nums, int numsSize)
{//异或int ret 0;//先异或0-n的所有数for(int i 0; i numsSize; i){ret ^ i;}//再将ret与数组所有数异或for(int i 0; i numsSize; i){ret ^ nums[i];}return ret;
}数组中出现的次数 同上可得此题采用异或的位运算是最合适的。
int* singleNumbers(int* nums, int numsSize, int* returnSize) {int ret 0;int i 0;int num1 0;int num2 0;int pos 0;int* arr (int*)malloc(2 * sizeof(int));//通过0对自身依次异或将两个单独的数的异或后的结果找出for (i 0; i numsSize; i){ret ^ nums[i];}//找到异或后结果的二进制序列找出为1的位数for (i 0; i 32; i){if ((ret i) 1 1){pos i;break;}}//找到位数后将按其他数的这个位数是否为1还是为0进行分离形成两组数分别自身异或最后剩下的就是单独的数。for (i 0; i numsSize; i){if ((nums[i] pos) 1 1){num1 ^ nums[i];}else{num2 ^ nums[i];}}arr[0] num1;arr[1] num2;*returnSize 2;return arr;
}
