只出现一次的数字

    技术2025-06-04  29

    只出现一次的数字 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 利用异或,相同的值异或为0,不同异或为1 即a^b^a = b; int singleNumber(vector<int>& nums) { int res = nums[0]; for (int i = 1; i < nums.size(); i++) { res = res ^ nums[i]; } return res; } 只出现一次的数字 III 给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。 vector<int> singleNumbers(vector<int>& nums) { vector<int> res; if (nums.size() <= 2) { return res; } int ret = 0; // 存储两个不同数的异或值 for (int i = 0; i < nums.size(); i++) { ret ^= nums[i]; } //两个不同数的异或值为1的那一位必然是两个值不同的位,通过该位将两个数分成两组 int div = 1; // 找到第一个为1的位 while ((div & ret) == 0) { div <<= 1; } int a = 0; int b = 0; for(int i = 0; i < nums.size(); i++) { if (div & nums[i]) { a ^= nums[i]; } else { b ^= nums[i]; } } res.push_back(a); res.push_back(b); return res; }
    Processed: 0.011, SQL: 9