建设银行对公网站,无锡seo管理,wordpress4.4,成都网页设计工资多少钱1.找只出现1次的数字,其余数出现n次
给你一个整数数组 nums #xff0c;除某个元素仅出现 一次 外#xff0c;其余每个元素都恰出现n次 。请你找出并返回那个只出现了一次的元素
当n等于2时 这道题可以使用异或运算来解决。我们知道#xff0c;异或运算有以下性质#xf…1.找只出现1次的数字,其余数出现n次
给你一个整数数组 nums 除某个元素仅出现 一次 外其余每个元素都恰出现n次 。请你找出并返回那个只出现了一次的元素
当n等于2时 这道题可以使用异或运算来解决。我们知道异或运算有以下性质
1.任何数和0进行异或运算都等于它本身。 2.任何数和它本身进行异或运算都等于0。 3.异或运算满足交换律和结合律。 假设有一个数组nums其中只有一个数出现了一次其他数都出现了两次。我们可以将数组中的所有数字进行异或运算得到的结果就是只出现了一次的那个数。因为其他数字都出现了两次所以它们的异或和会相互抵消只有那个只出现了一次的数会保留下来。
以下是使用异或运算找出一个整数数组中只出现了一次的数的C代码
int singleNumber(vectorint nums)
{int result 0;for (int num : nums) {result ^ num;}return result;
}当n2时 1.首先定义一个变量ans用来存储只出现了一次的数。 2.遍历32位二进制数对于每一位依次统计数组中所有数字在这一位上1出现的次数并将它们的和存储到变量total中。 3.如果total对n取余不为0说明只出现了一次的数在这一位上是1将1左移i位然后按位或运算到ans中。 4.最后返回变量ans就是只出现了一次的数。
class Solution {
public:int singleNumber(vectorint nums) {int ans 0;for (int i 0; i 32; i) {int total 0;for (int num: nums) {total ((num i) 1);}if (total % n) {ans | (1 i);}}return ans;}
};2.找只出现1次的数字的两个数字其余数出现2次本人只遇到这种类型欢迎补充
假设有一个数组nums其中有两个数出现了一次其他数都出现了两次。我们可以将数组中的所有数字进行异或运算得到的结果就是只出现了一次的两个数的异或和。因为其他数字都出现了两次所以它们的异或和会相互抵消只有那两个只出现了一次的数会保留下来。
我们可以通过找到异或和中第一个为1的位将数组中的所有数字分成两组一组在这一位上为1另一组在这一位上为0。这样只出现了一次的两个数就被分到了不同的组内而其他数字在同一组内。然后对于每一组内的数字我们可以分别进行异或运算得到只出现了一次的两个数。
class Solution {
public:vectorint singleNumber(vectorint nums){int ret 0;int i 0;for (i 0; i nums.size(); i){ret ^ nums[i];}int pos 0;while (pos 32){if (((ret pos) 1 ) 1){break;}pos;}int j 0;int result1 0;int result2 0;for (j 0; j nums.size(); j){if (((nums[j] pos) 1) 1){result1 ^ nums[j];}else{result2 ^ nums[j];}}vectorintresult(2);result[0] result1;result[1] result2;return result;}
};
