当前位置: 首页> 文旅> 艺术 > 推广普通话活动方案和总结_长沙本地推广联系电话_模板建站教程_小网站广告投放

推广普通话活动方案和总结_长沙本地推广联系电话_模板建站教程_小网站广告投放

时间:2025/7/11 14:39:06来源:https://blog.csdn.net/qq_54813250/article/details/144988442 浏览次数:0次
推广普通话活动方案和总结_长沙本地推广联系电话_模板建站教程_小网站广告投放

问题

问题描述

在一个班级中,每位同学都拿到了一张卡片,上面有一个整数。有趣的是,除了一个数字之外,所有的数字都恰好出现了两次。现在需要你帮助班长小C快速找到那个拿了独特数字卡片的同学手上的数字是什么。

要求:

  1. 设计一个算法,使其时间复杂度为 O(n),其中 n 是班级的人数。
  2. 尽量减少额外空间的使用,以体现你的算法优化能力。

测试样例

样例1:

输入:cards = [1, 1, 2, 2, 3, 3, 4, 5, 5]
输出:4
解释:拿到数字 4 的同学是唯一一个没有配对的。

样例2:

输入:cards = [0, 1, 0, 1, 2]
输出:2
解释:数字 2 只出现一次,是独特的卡片。

样例3:

输入:cards = [7, 3, 3, 7, 10]
输出:10
解释:10 是班级中唯一一个不重复的数字卡片。

约束条件

  • 1 ≤ cards.length ≤ 1001
  • 0 ≤ cards[i] ≤ 1000
  • 班级人数为奇数
  • 除了一个数字卡片只出现一次外,其余每个数字卡片都恰好出现两次

思路

这个问题的目的是找出一个数组中唯一一个未重复的数字,所有其他数字在数组中都出现了两次。对于这个问题,使用 异或运算 是非常高效的解决方法。我们可以通过以下步骤解决问题:

  1. 异或运算特性

    • a ^ a = 0:两个相同的数异或结果是 0。
    • a ^ 0 = a:任何数与 0 异或的结果是它本身。
    • 异或是交换律结合律的,意味着无论操作顺序如何,结果都是一样的。

    因此,对于数组中所有数字,我们进行逐个异或操作,成对的数字都会互相抵消(变为 0),最终留下的就是唯一一个未重复的数字。

  2. 解决方案

    • 初始化一个变量 uniqueNumber 为 0。
    • 遍历数组中的每个数字,并将其与 uniqueNumber 进行异或操作。
    • 最后 uniqueNumber 中存储的就是唯一未重复的数字。

具体步骤:

  1. 初始化 uniqueNumber 为 0。
  2. 遍历输入数组,对每个数字进行异或操作。
  3. 返回 uniqueNumber,它即为唯一的未重复数字。

解释:

输入示例 1:{1, 1, 2, 2, 3, 3, 4, 5, 5}

  • 目标:在这个数组中,数字 1, 2, 3, 5 都出现了两次,而 4 是唯一没有重复的数字。

  • 过程

    1. 初始化 uniqueNumber = 0
    2. 遍历数组,对每个数字进行异或操作。根据异或运算的特性,相同的数字异或结果是 0,不同的数字异或结果是它们自己。

    计算过程

    • uniqueNumber = 0 ^ 1 = 1(第一个数字是 1,结果是 1
    • uniqueNumber = 1 ^ 1 = 0(第二个数字是 1,结果是 0,因为 1 ^ 1 = 0
    • uniqueNumber = 0 ^ 2 = 2(第三个数字是 2,结果是 2
    • uniqueNumber = 2 ^ 2 = 0(第四个数字是 2,结果是 0,因为 2 ^ 2 = 0
    • uniqueNumber = 0 ^ 3 = 3(第五个数字是 3,结果是 3
    • uniqueNumber = 3 ^ 3 = 0(第六个数字是 3,结果是 0,因为 3 ^ 3 = 0
    • uniqueNumber = 0 ^ 4 = 4(第七个数字是 4,结果是 4
    • uniqueNumber = 4 ^ 5 = 1(第八个数字是 5,结果是 1
    • uniqueNumber = 1 ^ 5 = 4(第九个数字是 5,结果是 4

    最终,uniqueNumber 的值是 4,它是唯一未重复的数字。

输入示例 2:{0, 1, 0, 1, 2}

  • 目标:在这个数组中,数字 01 都出现了两次,而 2 是唯一没有重复的数字。

  • 过程

    1. 初始化 uniqueNumber = 0
    2. 遍历数组,对每个数字进行异或操作。

    计算过程

    • uniqueNumber = 0 ^ 0 = 0(第一个数字是 0,结果是 0
    • uniqueNumber = 0 ^ 1 = 1(第二个数字是 1,结果是 1
    • uniqueNumber = 1 ^ 0 = 1(第三个数字是 0,结果是 1,因为 0 ^ 0 = 0,所以结果是 1
    • uniqueNumber = 1 ^ 1 = 0(第四个数字是 1,结果是 0,因为 1 ^ 1 = 0
    • uniqueNumber = 0 ^ 2 = 2(第五个数字是 2,结果是 2

    最终,uniqueNumber 的值是 2,它是唯一未重复的数字。

输入示例 3:{7, 3, 3, 7, 10}

  • 目标:在这个数组中,数字 73 都出现了两次,而 10 是唯一没有重复的数字。

  • 过程

    1. 初始化 uniqueNumber = 0
    2. 遍历数组,对每个数字进行异或操作。

    计算过程

    • uniqueNumber = 0 ^ 7 = 7(第一个数字是 7,结果是 7
    • uniqueNumber = 7 ^ 3 = 4(第二个数字是 3,结果是 4
    • uniqueNumber = 4 ^ 3 = 7(第三个数字是 3,结果是 7
    • uniqueNumber = 7 ^ 7 = 0(第四个数字是 7,结果是 0
    • uniqueNumber = 0 ^ 10 = 10(第五个数字是 10,结果是 10

    最终,uniqueNumber 的值是 10,它是唯一未重复的数字。

代码

public class Main {public static int solution(int[] inp) {int uniqueNumber = 0; // 初始化一个变量来存储最终的结果for (int num : inp) { // 遍历输入的数组uniqueNumber ^= num; // 对每个数字进行异或操作}return uniqueNumber; // 返回最终找到的单独数字}public static void main(String[] args) {// 测试用例System.out.println(solution(new int[] { 1, 1, 2, 2, 3, 3, 4, 5, 5 }) == 4);System.out.println(solution(new int[] { 0, 1, 0, 1, 2 }) == 2);System.out.println(solution(new int[] { 7, 3, 3, 7, 10 }) == 10);}
}

提交结果

关键字:推广普通话活动方案和总结_长沙本地推广联系电话_模板建站教程_小网站广告投放

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: