面试题 17.04. 消失的数字

简介: 面试题 17.04. 消失的数字

目录

消失的数字

方法1

方法2

方法3

找单身狗

消失的数字

题目如下:


a43b4f8f31b64fd394ecb97407e61769.png

方法1

方法1的思想是先将给定的数组排序,然后查看从哪个下标开始,下标和对于位置元素的值不同,那么消失的数字就是那个下标



7ac95218f98b48a39ba5be6a7c6503e1.png



但是在常见的排序算法中,最快的快排的时间复杂度是O(n*logn),所以不符合题意


方法2

可以看出,给定数组其实就是一个等差为1的等差数列中缺少一个数字

所以我们可以计算出这个等差数列的和,再一次减去给定数组中每个元素的值,最后剩下的值就是消失的数字。


代码如下:


int missingNumber(int* nums, int numsSize)
{
  int sum = numsSize * (numsSize + 1) / 2;
  for (int i = 0; i < numsSize; i++)
  {
  sum = sum - nums[i];
  }
  return sum;
}


方法3

方法3的思想是运用位操作符中的按位异或^


按位异或的一些特点:


1.对应的二进制位:相同位0,相异为1

2.a^a = 0

3.a^0 = a

4.异或支持交换律


所以我们可以将给定数组中的每个元素进行按位异或操作,然后再与一个[0,numsSize]数组中每个元素进行按位异或,最终得到的值就是消失的数字



2b0db4989fca4894b0d6ffef65a97821.png




代码如下:


int missingNumber(int* nums, int numsSize) {
    int n = 0;
    for (int i = 0; i < numsSize; i++)
    {
        n ^= nums[i];
    }
    for (int i = 0; i <= numsSize; i++)
    {
        n ^= i;
    }
    return n;
}


找单身狗

上一道题最主要最有意思的做法就是运行按位异或计算


下面也是一道有关按位异或运算的题:


一个数组中只有两个数字是出现一次,其他所有数字都出现了两次。

编写一个函数找出这两个只出现一次的数字。


根据上一题的思想,我们可以将两个单独的数字分到不同“组”中,再将两个“组”中的每个数字进行按位异或,最后得到2个单身狗


以数组[1,2,3,4,5,1,2,3,4,6]为例:

将这些数字都按位异或 1^2^3^4^5^1^2^3^4^6,最终可以得到5^6

5的二进制是 0101

6的二进制是 0110

5^6的值位为0011


以下是将数组元素依次异或的代码:


void singal_dog(int* nums, int size, int* singal_arr)
{
  int val = 0;
  for (int i = 0; i < size; i++)
  {
  val ^= nums[i];
  }
}


我们可以根据某些特点,将元素分为2组,例如二进制最后一位数字是否为0,或是否为1


所以 以最后一位数字是否为0进行分组,为0分一组,不是0分一组:




30fb7f8108634e3095335569cef6b765.png




可以看到将这2组依次进行按位异或就可以得到单生狗


那么怎么能知道这个数组中的数字是从哪位开始有区别的呢?

答案就是通过之前的 5^6的值得知


5^6的值位为0011,因为是按位异或,所以那位值为1,哪位就不同

所以可以看到,这一组数字就可以通过最后一位数字来分组


下面是找到有区别可以分组的那一位数字的代码:

void singal_dog(int* nums, int size, int* singal_arr)
{
  int pos = 0;
  for (int i = 0; i < 32; i++)
  {
  if (((val >> i) & 1) == 1)
  {
    pos = i;
    break;
  }
  }
}
1


最后,将2组代码依次按位异或,就可以得到单身狗


下面是完整代码:


void singal_dog(int* nums, int size, int* singal_arr)
{
  int val = 0;
  for (int i = 0; i < size; i++)
  {
  val ^= nums[i];
  }
  int pos = 0;
  for (int i = 0; i < 32; i++)
  {
  if (((val >> i) & 1) == 1)
  {
    pos = i;
    break;
  }
  }
  for (int i = 0; i < size; i++)
  {
  if (((nums[i] >> pos)&1) == 1)
  {
    singal_arr[0] ^= nums[i];
  }
  else
  {
    singal_arr[1] ^= nums[i];
  }
  }
}
int main()
{
  int arr[] = { 1,2,3,4,1,2,3,4,5,6 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  int singal[2] = { 0 };
  singal_dog(arr, sz,singal);
  printf("%d %d", singal[0], singal[1]);
  return 0;
}


目录
相关文章
|
Java API
Java 8 时间和日期 API
Java 8 时间和日期 API
109 1
|
人工智能 算法 vr&ar
计算机图形学
计算机图形学
178 1
|
存储 负载均衡 中间件
构建可扩展的分布式数据库:技术策略与实践
【8月更文挑战第3天】构建可扩展的分布式数据库是一个复杂而具有挑战性的任务。通过采用数据分片、复制与一致性模型、分布式事务管理和负载均衡与自动扩展等关键技术策略,并合理设计节点、架构模式和网络拓扑等关键组件,可以构建出高可用性、高性能和可扩展的分布式数据库系统。然而,在实际应用中还需要注意解决数据一致性、故障恢复与容错性以及分布式事务的复杂性等挑战。随着技术的不断发展和创新,相信分布式数据库系统将在未来发挥更加重要的作用。
|
SQL 存储 数据库
爆肝!一看就懂的《SQL 语言知识体系》【建议收藏】(中)
爆肝!一看就懂的《SQL 语言知识体系》【建议收藏】
196 1
|
11月前
|
监控 测试技术 网络虚拟化
如何提高系统的可用性时间
提高系统可用性时间的关键在于优化设计、强化监控与维护。通过冗余配置、故障转移、定期更新和实时监控等手段,可以有效减少系统停机时间,确保服务稳定运行。
|
开发框架 NoSQL 关系型数据库
基于SqlSugar的开发框架循序渐进介绍(27)-- 基于MongoDB的数据库操作整合
基于SqlSugar的开发框架循序渐进介绍(27)-- 基于MongoDB的数据库操作整合
|
JSON 小程序 JavaScript
微信小程序快速入门开发指南(二)
微信小程序快速入门开发指南(二)
|
存储 SQL 缓存
MySQL之深入InnoDB存储引擎——物理文件
一、参数文件 当 MySQL 实例启动时,数据库会先去读一个配置参数文件,用来寻找数据库的各种文件所在位置以及指定某些初始化参数。在默认情况下,MySQL 实例会按照一定的顺序在指定的位置读取,没有参数文件也可以运行,这时所有的参数值取决于编译 MySQL 时指定的默认值和源代码中指定参数的默认值。
video播放中页面上画线条-坐标点画图demo效果(整理)
video播放中页面上画线条-坐标点画图demo效果(整理)
|
缓存 JSON 网络协议
38. 一份tcp、http面试指南,常考点都给你了
38. 一份tcp、http面试指南,常考点都给你了
225 0
38. 一份tcp、http面试指南,常考点都给你了