小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

Leetcode题目解析(191021)

2019年10月21日 694点热度 0人点赞 0条评论

Leetcode 448:找到所有数组中消失的数字

题目描述

给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例

输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]

解题思路

平时我们会怎么做呢?我们会新建一个长度为nums中最大数字的数组flag,且全部初始化为0;然后遍历原来的nums中的每一个元素m,令flag[m-1]=1;这样的话,flag中所有不为1的元素再加上1就是缺失的元素,这样就能保证时间复杂度是O(n)。

但是这里我们不能额外空间,那我们该怎么办呢?其实也很简单,我们将置为1的思路转变为加上一个非常大的数,使原来为0的位置上的数字远远比不上它大就可以了。所以这里我们可以加上数组的尺寸。

这样,对于nums中的数字m,对nums[m-1]加上nums.size()。这样就区分开了,那么对于nums中不存在的数字n,nums[n-1]就一定小于等于nums.size()。

当然我们还有注意一件事情,即这个数字有可能已经被加了nums.size(),所以在实际获取m-1的时候通常取余。

代码实现

vector<int> findDisappearedNumbers(vector<int>& nums) {
    vector<int> res;
    if (nums.empty())
        return res;
    for (int i = 0; i < nums.size(); i++)
    {
        int ind = (nums[i] - 1) % nums.size();//获取到当前位的数字-1是多少,假设为ind(因为数组下标从0开始)
        nums[ind] += nums.size();//然后将第Ind位加上数组长度
    }
    //如果缺失了m,那么在第m-1位的数字肯定没有加上数组的长度,那么这一位必然小于等于数组的长度。
    //其实这个题还是类似于设置一个flag数组然后有这个数字则置为1(相当于本题中的加上数组长度),
    //没有这个数字则置为0(相当于本题的不加)
    for (int i = 0; i < nums.size(); i++)
    {
        if (nums[i] <= nums.size())
            res.push_back(i + 1);
    }
    return res;

}

算法性能

执行用时:116ms
内存消耗:14.8MB
超过了96.12%的C++提交记录。

Leetcode 461:汉明距离

题目描述

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y,计算它们之间的汉明距离。

注意:
0 ≤ x, y < 2^31.

示例

输入: x = 1, y = 4

输出: 2

解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑

上面的箭头指出了对应二进制位不同的位置。

解题思路

看代码即可,非常简单。

代码实现

int hammingDistance(int x, int y)
{
    int count = 0;
    while (x != 0 || y != 0)
    {
        if ((x & 1) != (y & 1))
            ++count;
        x >>= 1;
        y >>= 1;

    }
    return count;
}

代码性能

用时:4ms
内存:8.3MB

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年10月21日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
安装package control的几种方法 汉诺塔问题 C++中的cin, cin.getline, getline等混合使用时不能输入直接执行下一行的问题 “我们的高中”三部曲之二即将开始制作 论文阅读笔记20190521 2014年寒假(C语言程序设计)学习、复习计划及完成情况表
标签聚合
Python 鸟哥的linux私房菜 leetcode Java linux 高中 生活 算法 学习 python学习
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号