算法练习:只出现一次的数字

2024-01-10 09:44:19

题目:

  • 你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
  • 你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
    示例 1 :
输入:nums = [2,2,1]
输出:1

实现:

1.main方法

public static void main(String[] args) {
    int[] nums = {4, 1, 2, 1, 2};
    // 方式一:
    way1(nums);
    // 方式二:
    way2(nums);
}

2. 方式一:

/**
 * 方式一:使用 HashSet实现
 *
 * @param nums
 */
private static void way2(int[] nums) {
    // 获取数组只有一个的元素
    HashSet<Integer> hashSet = new HashSet<>();
    for (int num : nums) {
        if (!hashSet.add(num)) {
            hashSet.remove(num);
        }
    }
    int next = hashSet.iterator().next();
    System.out.println("way1: " + next);
}

原理:

  • 使用HashSet的结构特性实现:主要使用HashSet的不可重复性
    在这里插入图片描述

3. 方式二:

/**
 * 方式二:使用 异或实现
 *
 * @param nums
 */
private static void way1(int[] nums) {
    // 使用异或获取结果
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    System.out.println("way2: " + result);
}

原理:

  • 使用异或的特性实现

异或运算的规则如下:

  • 如果两个对应位的数相同,则结果为0。
  • 如果两个对应位的数不同,则结果为1。

简单的异或案例:

public class XORExample {
    public static void main(String[] args) {
        int num1 = 5;  // 二进制:0101
        int num2 = 3;  // 二进制:0011

        // 使用异或运算
        int result = num1 ^ num2;

        System.out.println("num1 异或 num2 的结果:" + result);  // 输出:6
    }
}

在这个例子中,我们有两个整数 num1 和 num2,它们的二进制表示分别为 0101 和 0011。通过异或运算,对应位上相同的数会得到0,不同的数得到1。因此,num1 ^ num2 的结果为 0110,对应的十进制值为6。

参考:

力扣:https://leetcode.cn/leetbook/read/top-interview-questions/xm0u83/

文章来源:https://blog.csdn.net/m0_72560900/article/details/135447585
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。