LeetCode--268. Missing Number_given an array containing n distinct numbers taken-程序员宅基地

技术标签: Leetcode题解  数学问题  Math  

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?


思路:

1.数学题,根据公式求出前n项和应该是多少再减去实际值即可。

附等差数列公式: 1) 第n项, an=a1+(n-1)d。
                                  2) 前n项和,Sn=n*a1+n(n-1)d/2或Sn=n(a1+an)/2


参考代码:
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n=nums.size()+1,sum=0;
        for(int i=0;i<n-1;++i){
            sum+=nums[i];
        }
        return n*(n-1)/2-sum;
    }
};

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/vir_lee/article/details/80501571

智能推荐

Android Studio 超详细 安装SDK 教程_andriod studio 需要安装什么-程序员宅基地

文章浏览阅读3.5w次,点赞32次,收藏121次。Android SDK Manager 所需要下载的文件刚开始接触Android应用开发,工欲善其事,必先利其器。1.首先这三个是必须安装的。2.选择你要下载的SDK版本,这里以Android10为示例。选完之后点install 10 packges3.等待下载就行了。..._andriod studio 需要安装什么

CCS7.3 安装使用教程_如何把ccs文件转为keil-程序员宅基地

文章浏览阅读1.1w次,点赞2次,收藏9次。CCS7.3 安装使用教程•Code Composer Studio IDE,是TI的集成开发环境。 Code Composer Studio Desktop IDE for all TI microcontrollers, processors, and wireless connectivity platforms。TI所有的产品都可以用ccs进行开发。 1.首先到TI官网进行下载最新本_如何把ccs文件转为keil

Android 各类优秀依赖库 等各位砖友来搬_android好用的用于检查输入的依赖-程序员宅基地

文章浏览阅读2.8k次,点赞8次,收藏23次。有很多类型的开源库 希望能够帮助到您抽屉菜单MaterialDrawer ★7337 - 安卓抽屉效果实现方案 Side-Menu.Android ★3865 - 创意边侧菜单 FlowingDrawer ★1744 - 向右滑动流动抽屉效果 SlidingRootNav ★1338 - 仿DrawerLayout的ViewGroup FantasySlide ★1049..._android好用的用于检查输入的依赖

Python求多个list的交集、并集、差(补)集的方法_python 多个list求并集-程序员宅基地

文章浏览阅读1.5w次,点赞9次,收藏51次。文章目录摘要1.求多个list的交集2.求多个list的并集3.求多个list的差(补)集 - 即获取特定1个list中有,其他list都没有的元素4.求在多个list中只出现过1次的元素组成的集合摘要本文主要介绍在Python下求两个list的交集、并集、差(补)集、对称差集的方法,如何在Python中对变量名进行动态地定义,介绍以下两种常用的情况:1.定义如a1=1,a2=2,a3=3这..._python 多个list求并集

python动图存储为视频_matplotlib动态图和视频保存-程序员宅基地

文章浏览阅读1k次。FuncAnimation类class matplotlib.animation.FuncAnimation(fig, func, frames=None, init_func=None,fargs=None, save_count=None, **kwargs)参数fig : matplotlib.figure.Figure对象,可以理解为画布func : 函数(callable),每一帧被调用..._把刷新的fig保存为视频

JAVA中ResourceBundle使用详解-程序员宅基地

文章浏览阅读9.1w次,点赞56次,收藏227次。JAVA中ResourceBundle使用详解这个类主要用来解决国际化和本地化问题。国际化和本地化可不是两个概念,两者都是一起出现的。可以说,国际化的目的就是为了实现本地化。比如对于“取消”,中文中我们使用“取消”来表示,而英文中我们使用“cancel”。若我们的程序是面向国际的(这也是软件发展的一个趋势),那么使用的人群必然是多语言环境的,实现国际化就非常有必要。而ResourceBund

随便推点

基于javaweb的水果蔬菜商城批发系统(java+ssm+jsp+jquery+mysql)_蔬菜批发 系统-程序员宅基地

文章浏览阅读597次。基于javaweb的水果蔬菜商城批发系统(java+ssm+jsp+jquery+mysql)运行环境Java≥8、MySQL≥5.7、Tomcat≥8开发工具eclipse/idea/myeclipse/sts等均可配置运行适用课程设计,大作业,毕业设计,项目练习,学习演示等功能说明_蔬菜批发 系统

.net core 控制台程序发布并运行在 centos(便携应用方式)_控制台net7 怎么发布到centos-程序员宅基地

文章浏览阅读9.6k次。编写一个console app并发布到centos1.新建一个.net core控制台程序2. 直接发布,选择目标运行为linux3.将Release\netcoreapp2.0目录下的pulish目录复制到centos中4.修改publish下的执行文件为可执行(文件属性中可修改)5.在命令行窗口中可执行如果执行报错:Failed to load , error: libunwind.so.8:..._控制台net7 怎么发布到centos

基于SSM 的图书馆管理系统_图书管理ssm-程序员宅基地

文章浏览阅读1.5k次。基于SSM 的图书馆管理系统拥有两个角色,分别为管理员和学生。具体功能如下:**管理员**:查看、添加图书,查看添加学生,借还管理,修改密码等**学生**:查加检索图书、查看个人信息、查看个人借阅情况、修改密码_图书管理ssm

USB转串口那些事儿—USB转串口工作原理及应用-程序员宅基地

文章浏览阅读2.9w次,点赞37次,收藏189次。USB转串口即实现计算机USB接口到物理串口之间的转换。可以为没有串口的计算机或其他USB主机增加串口,使用USB转串口设备等于将传统的串口设备变成了即插即用的USB设备。USB虚拟串口应用特点:USB应用广泛,支持热插拔,传输速度快。仿真标准串口,用于升级原串口设备,或通过USB增加额外串口。串口应用程序完全兼容,无需修改。支持各类操作系统,如:Windows/Linux/Android/macOS。二、工作原理USB主机检测到USB转串口设备插入后,首先会对设备复..._usb转串口

第2章:指令系统的设计_等长扩展码什么意思啊-程序员宅基地

文章浏览阅读2.7k次。指令系统是计算机系统结构的主要内容,是软硬件交界面的主要部分。区别不同指令系统结构的主要因素:CPU中用来存储操作数的数据单元类型对于不同类型的结构,操作数的位置、个数以及操作数的给出方式(显式或隐式)也会不同用 指令字中的操作数字段 给出比如,直接给出操作数的值使用事先约定好的单元堆栈型结构中,操作数隐式给出,栈顶两个元素被弹出参与运算,计算结果被压入栈中累加器型结构中,累加器内的操作数是隐式的,另一个操作数是显式给出的比如:add X 其中累加器中的数据是隐式的,X是显式给出的。在通用寄存器型结构中,_等长扩展码什么意思啊

cocos2d 游戏引擎发展历史_cocos最早起源-程序员宅基地

文章浏览阅读2.9k次。这个帖子纯属为了梳理一下近日以来凌乱是思维,打算搞cocos很久了,可是由于工作原因一直都是自己摸索,断断续续,今天难得有空,把cocos发展主线梳理一下,有了脉络,学习起来就不会乱。cocos由来(百度百科)Cocos2D的诞生2005年,Ricardo和朋友萌生了用Python语言 “一星期编写一个游戏”的想法。在2005~2007年间,他们设计了许多种这样的游戏。_cocos最早起源