Leetcode — 只出现一次的数

时间:2021-6-12 作者:qvyue

1.只出现一次的数(136 – 易)

题目描述:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 :

输入: [2,2,1]
输出: 1

输入: [4,1,2,1,2]
输出: 4

思路

法1:本题比较常规的解法是用集合进行记录,最终返回集合中的唯一元素,代码实现如下,但这里空间复杂度O(n)!

法2:先排序后比较有没有落单的,落单返回,时间复杂度O(nlogn),空间复杂度O(1)。

法3:根据异或对象相同为0,不同为1的规则,可以推导出一些性质

  • 0 ⊕ a = a
  • a ⊕ a = 0

此外,异或满足交换律以及结合律

代码实现:

解法1:

public int singleNumber(int[] nums) {
    HashSet set = new HashSet();
    for (int i = 0; i 

ps:这里注意迭代器和数据结构中的链表一样,有个header指针,header->next()就是链表中第一个元素…… 如下所示:

 pre  1  2  3  4

开始header指针指向pre,当执行一次iterator().next()就是返回指针所指的元素,即返回1,本题中返回那个唯一元素。

解法2:

public int singleNumber(int[] nums) {
    if (nums.length == 1) return nums[0];
    int i = 1;
    Arrays.sort(nums);
    for ( ; i 

解法3:

public int singleNumber(int[] nums) {
    int ans = 0;
    for (int i = 0; i 

2.只出现一次的数(137 – 中)

题目描述:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 :

输入: [2,2,3,2]
输出: 3

输入: [0,1,0,1,0,1,99]
输出: 99

思路

法1:和1不同的是,本题重复数字变成3个,可以用HashMap来实现计数,但时间复杂度O(n);

法2:和案例1解法2思路相同,先排序,后比较;

法3:参考 这里 的一个解法。我们把数字放眼到二进制形式。

假如例子是 1 2 6 1 1 2 2 3 3 3,   3 个 1, 3 个 2, 3 个 3,1 个 6
1    0 0 1
2    0 1 0 
6    1 1 0 
1    0 0 1
1    0 0 1
2    0 1 0
2    0 1 0
3    0 1 1  
3    0 1 1
3    0 1 1      
看最右边的一列 1001100111 有 6 个 1
再往前看一列 0110011111 有 7 个 1
再往前看一列 0010000 有 1 个 1
我们只需要把是 3 的倍数的对应列写 0,不是 3 的倍数的对应列写 1    
也就是 1 1 0,也就是 6。

原因的话,其实很容易想明白。如果所有数字都出现了 3 次,那么每一列的 1 的个数就一定是 3 的倍数。之所以有的列不是 3 的倍数,就是因为只出现了 1 次的数多贡献出了 1

所以所有不是 3 的倍数的列写 1(多出的数有贡献),其他列写 0(无贡献) ,就找到了这个出现 1 次的数。

本解法也可以进行推广,即是n的倍数列写1,其他列写0,找到其余元素都出现n次时,出现1次的元素。

代码实现:

解法1:

public int singleNumber(int[] nums) {
    HashMap map = new HashMap();
    for (int i = 0; i 

解答2:

public int singleNumber(int[] nums) {
    if (nums.length == 1) return nums[0];
    int i = 2;
    Arrays.sort(nums);
    for (i = 2; i 

解法3:外层循环32位二进制,可以认为时间复杂度为O(n)

public int singleNumber(int[] nums) {
    int ans = 0;
    //考虑每一位
    for (int i = 0; i >> i & 1) == 1) {
                count++;
            }
        }
        //1 

ps:注意先位运算再进行逻辑运算。java优先级口诀:单目乘除为(位)关系,逻辑三目后赋值。

  • 单目:单目运算符+ –(负数) ++ — 等
  • 乘除:算数单目运算符* / % + –
  • 为:位移单目运算符> >>>
    • 带符号右移>>(相当于除以2):正数右移高位补0,负数右移高位补1。
    • 无符号右移>>>:无论正数负数,高位统统补0。
  • 关系:关系单目运算符> =
  • 逻辑:逻辑单目运算符&& || & | ^
  • 三目:三目单目运算符A > B ? X : Y
  • 后:无意义,仅仅为了凑字数
  • 赋值:赋值 =
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。