| |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
-> 数据结构与算法 -> 【LeetCode】经典算法 找出一个数组中只出现一次的数 -> 正文阅读 |
|
[数据结构与算法]【LeetCode】经典算法 找出一个数组中只出现一次的数 |
问题描述:一个数组中只有一个数字是出现一次,? 思路:最简单直观的方法,我们用两个for循环,外循环用i,内循环用j表示,数组长度用len表示 外循环执行一次,内循环执行len-1次,逐一比较,如果相等就给count++,外循环一次结束,如果count = 1,说明这个数就出现了一次,打印arr[i]即可 代码示例:
程序测试:? ? 当然这种方法也可以求数组中任意出现了一次的数字,不过时间复杂度为O(n^2),空间复杂度为O(1),不推荐。 那么有没有更好的方法呢?从节约时间复杂度或空间复杂度着手 当然有的啦 那么这个题的突破口在哪里呢?注意这个数组的特殊性:其它数字都出现了两次,只有一个数出现了一次。可以想到运用异或运算 异或运算有一个性质:任何数异或它自己,结果都是0,而0与任意数按位异或其结果都为该任意数;这样如果题目变成只有一个数字只出现一次,其他数字均出现两次,这样我们从头到尾异或数组中的每一个数字,那么最终的结果就是只出现一次的数字。如此一来,我们的时间复杂度就变成了O(n),空间复杂度为O(1)。? 注意:位运算符运算,参与的数字应该为二进制 异或:如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。 举个栗子:2 1 3 2 3 2?xor?1 :0010 ^0001 -->0011 ==3 3?xor?3: 0011 ^0011 -->0000==0 0?xor?2: 0000 ^0010 -->0010==2 2?xor 3: 0010 ^0011 -->0001==1? ? ? 结果为1 代码示例如下:
如果你会了这段代码,那么真正的题目是:一个整型数组里除了两个数字外,其他的数字都出现了两次,要找出这两个数字。这应该怎么写呢?(要求时间复杂度为O(n),空间复杂度为O(1))。其实思想也不难? ? ? ? ? ? ? 思路:根据上面的讲解,我们知道一个整型数组中,若只有两个数字只出现一次,其他数字都出现了两次,那么把数组中的所有遍历异或一遍的结果就是只出现一次的两个数字相异或的结果。 如果可以把数组中的数字分成两个子数组,每个数组里面包含一个只出现一次的数字,其他的数字都出现两次,这样按照上面的方法就可以分别求出只出现一次的数字了。 那么依照什么条件来将所有数字分成两个数组呢?我们来举一个栗子 我们先定义一个 int arr[] = { 1, 2, 3, 3, 2, 1, 4, 5 }; 把数组中所有的元素分组 1--> 0001 4和5相异或的结果: 0001 接下来我们按照二进制第一位相同的来划分两个数组
总结方法:首先,我们从头到尾异或数组中的每一个数字,那么得到的结果将是这两个只出现了一次的数字异或后的结果(因为其他出现了两次的数字都在异或中抵消了)。由于这两个数字不相同,所以它们的异或结果的二进制表示中至少有一位是1。我们先找到第一个为1的位的位置,。然后我们以这一位是否为1,把原数组分成两个子数组,第一个数组中每个数的这一位都为1,第二个数组中的每个数的这一位都为0,因为两个相同的数字的任意一位都是相同的,所以相同的数肯定分在同一组,这样我们就实现了划分子数组的效果。接下来我们进行代码示例 ? 代码示例:
程序演示:
|
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年1日历 | -2025/1/9 16:04:47- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |