260.只出现一次的数字 III

本文主要是介绍260.只出现一次的数字 III，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

260.只出现一次的数字 III

解题思路：

利用异或规则：相同数字异或结果为0,一个数字与0异或结果不变

package leadcode;import java.util.Arrays;/*** @author : icehill* @description : 只出现一次的数字III* 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。* 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。* 进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？* 示例 1：* 输入：nums = [1,2,1,3,2,5]* 输出：[3,5]* 解释：[5, 3] 也是有效的答案。* 示例 2：* 输入：nums = [-1,0]* 输出：[-1,0]* 示例 3：* 输入：nums = [0,1]* 输出：[1,0]* 提示：* 2 <= nums.length <= 3 * 10^4* -2^31 <= nums[i] <= 2^31 - 1* 除两个只出现一次的整数外，nums 中的其他数字都出现两次* 来源：力扣（LeetCode）* 链接：https://leetcode-cn.com/problems/single-number-iii* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。* 解题思路：* 这道题有点像脑筋急转弯，说难也不难，我们需要利用异或的特性之一，相同数字异或为0* 如果是只有一个数字出现一次的数组，则全部异或即可得到，现在是两个，如果我们进行分组，就可以解决* 分组的条件需要满足：* 1.这两个元素：a、b分在不同组* 2.相同元素分在同个组* 分组过程：把所有元素进行异或，最终得到的是：a^b* 要把a、b分组，只需要根据某个位是否为1或者0，就肯定可以确定ab不在同个组，* 至于其他元素相同元素该位置肯定也是相同的，所以这样分组是没问题的* @date : 2021-05-27*/
public class Solution260 {public static void main(String[] args) {int[] nums = {1, 2, 1, 3, 2, 5};int[] nums2 = {-1, 0};Solution260 solution260 = new Solution260();System.out.println(Arrays.toString(solution260.singleNumber(nums)));System.out.println(Arrays.toString(solution260.singleNumber(nums2)));}public int[] singleNumber(int[] nums) {int res = 0;for (int i = 0; i < nums.length; i++) {res ^= nums[i];}int single = 1;while ((single & res) == 0) {single <<= 1;}int a = 0, b = 0;for (int i = 0; i < nums.length; i++) {if ((nums[i] & single) == single) {a ^= nums[i];} else {b ^= nums[i];}}return new int[]{a, b};}
}

这篇关于260.只出现一次的数字 III的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---