当前位置: 首页 > news >正文

Leecode之面试题消失的数字

一.题目及剖析

https://leetcode.cn/problems/missing-number-lcci/description/

数组nums包含从0n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?

注意:本题相对书上原题稍作改动

示例 1:

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

示例 2:

输入:[9,6,4,2,3,5,7,0,1]
输出:8

方法有很多,这里将两种时间复杂度为O(N)的方法

二.思路引入

第一种方法

先将0-n的总和求出来,在求出数组的总和,在做差就能得到消失的数字,不过要注意的是数据有可能溢出,这个方法很简单就不再进行代码演示了

第二种方法

利用a^a==0的特性,给定一个x异或0-n,再异或数组中的元素,最后剩下的就是消失的数字

三.代码引入

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

http://www.lryc.cn/news/301747.html

相关文章:

  • STM32的三种下载方式
  • 华为 huawei 交换机 接口 MAC 地址学习限制接入用户数量 配置示例
  • 使用Python生成二维码的完整指南
  • 排序前言冒泡排序
  • 红队笔记Day3-->隧道上线不出网机器
  • C 练习实例70-求字符串长度
  • HarmonyOS—@State装饰器:组件内状态
  • Linux系统——防火墙拓展及重点理解
  • 阿里云短信验证码的两个坑
  • c入门第十五篇——学而时习之(阶段性总结)
  • 抽象的前端
  • UPC训练赛二十/20240217
  • 【51单片机】LCD1602(江科大)
  • conda与pip的常用命令
  • 你知道什么是物联网MQTT么?
  • P8 pair vector
  • 奇异值分解(SVD)的应用——图像压缩
  • RTDETR改进系列指南
  • 类和结构体的区别
  • 利用Excel模拟投币试验
  • WebService接口测试
  • 语音唤醒——
  • typeScript 类型推论
  • JavaScript 设计模式之代理模式
  • JavaScript 对象判断
  • Android下SF合成流程重学习之onMessageInvalidate
  • 基于SpringBoot+WebSocket+Spring Task的前后端分离外卖项目-订单管理(十七)
  • 【Java多线程进阶】JUC常见类以及CAS机制
  • Python算法100例-1.7 最佳存款方案
  • ADO世界之FIRST