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

消失的数字,旋转数组(leetcode 一题多解)

目录

一、消失的数字

思路一(暴力求解)代码实现:

思路二(数列的思想)代码实现:

思路三(异或的运用)代码实现:

 二、轮转数组

思路一(暴力求解)代码实现:

思路二使用额外的空间(以空间换时间)代码实现:

思路三(三步逆置)


一、消失的数字

思路如下图:

思路一(暴力求解)代码实现:

排序好后一一查找。

此处不建议使用该方法,因为时间复杂度过大。


int missingNumber(int* nums, int numsSize)
{int i = 0;int j = 0;int flag = -1;//利用冒泡排序思想进行排序for (i = 0; i < numsSize - 1; i++){for (j = 0; j < numsSize - 1 - i; j++){if (nums[j] > nums[j + 1]){int tmp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = tmp;}}}//一个个查找for (i = 0; i < numsSize; i++){if (i != nums[i]){flag = i;break;}}return i;
}

思路二(数列的思想)代码实现:

此处代码就开始简化了:时间复杂度为O(N),先用上等差数列的公式求前num个数字之和,再一一减去nums数组中的元素,最后得到的就是消失的数字!

int missingNumber(int* nums, int numsSize)
{int i=0;int sum=0;//前numsSize个数字相加,等差数列求和sum = (numsSize+1)*numsSize/2;//减去nums数组中的所有值的和for(i=0;i<numsSize;i++){sum-=nums[i];}return sum;
}

思路三(异或的运用)代码实现:

利用了异或操作符
首先讲解一下这个操作符(^):
  这个操作符是对二进制来用的,相同为零相异为一
这个操作符有几个特点
  1.n^0 = n
  2.n^n = 0
  3.满足交换律,如:(a^b) ^ c =a^(b^c)

如果想知道更多操作符的使用请移步到:操作符(笔记)-CSDN博客

思路:用0先跟0~numsSize中数据异或,再跟nums数组中所有元素异或,最后的值就是所要找的值 

效果如下:

0^1^2^...中间有消失的数...^n ^1^2^...中间消失的数不在这里...^n = 0^中间有消失的数 =

中间有消失的数

int missingNumber(int* nums, int numsSize)
{int x = 0;int i = 0;//先跟0-numsSize中数据异或for (i = 1; i <= numsSize; i++){x = x ^ i;}//跟nums数组中数据异或for (i = 0; i < numsSize; i++){x = x ^ nums[i];}return x;}

 二、轮转数组

思路如下图所示

思路一(暴力求解)代码实现:

void rotate(int* nums, int numsSize, int k) {//如果k>=numsSize,则k=k%numsSize,减少循环次数if (k >= numsSize){k %= numsSize;}//轮转的次数for (int j = 1; j <= k; s++){//记录数组最后一个元素的值int tmp = nums[numsSize-1];//每一次的轮转数组的变化for (int i = numsSize - 1; i > 0; i--){nums[i] = nums[i - 1];	}//把记录下来的值赋给数组首元素nums[0] = tmp;}
}

思路二使用额外的空间(以空间换时间)代码实现:

牺牲存储空间为代价,直接在栈上开辟一块新的存储空间

void rotate(int* nums, int sz, int k)
{//开辟与nums数组一样大小的空间int* tmp = (int*)malloc(sizeof(int) * sz);int i = 0;//如果k>=size,则k=k%size,减少循环次数if (k >= sz){k %= sz;}//先把后sz-k-1个元素拷贝到tmp中去for (i = 0; i < k; i++){tmp[i] = nums[sz - k + i];}//再把前k-1个元素拷贝到tmp中去for (i = 0; i < sz-k; i++){tmp[k+i] = nums[i];}//最后,把tmp的内容拷贝到nums中去for (i = 0; i < sz; i++){nums[i] = tmp[i];}
}

思路三(三步逆置)

如果k>=numsSize时,取余数

因为,逆置8次和逆置1次效果是相同的

void reverse(int* nums, int left, int right) {while (left < right) {int tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;left++;right--;}
}void rotate(int* nums, int numsSize, int k) {if(k>=numsSize){k %= numsSize; // 如果k大于等于数组长度,先对k取余}reverse(nums, 0, numsSize - k - 1);//注意控制下标reverse(nums, numsSize - k, numsSize - 1);reverse(nums, 0, numsSize - 1);
}

相关文章:

消失的数字,旋转数组(leetcode 一题多解)

目录 一、消失的数字 思路一&#xff08;暴力求解&#xff09;代码实现&#xff1a; 思路二&#xff08;数列的思想&#xff09;代码实现&#xff1a; 思路三&#xff08;异或的运用&#xff09;代码实现&#xff1a; 二、轮转数组 思路一&#xff08;暴力求解&#xff09…...

肠道菌群16s检测粪便采样工具包 粪便采样套装

肠道菌群16s检测是一种常见的分子生物学技术&#xff0c;用于研究人体肠道中的微生物群落。该技术通过分析16s rRNA基因序列&#xff0c;可以快速、准确地鉴定并定量不同种类的肠道微生物。 肠道菌群16s检测通常通过采集粪便样本进行分析。在实验室中&#xff0c;通过提取微生物…...

实现领域驱动设计-07-领域服务

领域中的服务表示一个无状态的操作&#xff0c;它用于实现特定于某个领域的任务。当某个操作不适合放在聚合和值对象上时&#xff0c;为了避免过程式的编程方式&#xff0c;最好的方式便是使用领域服务来实现该操作。 什么是领域服务? 当领域中的某个操作过程或转换过程不是实…...

井盖位移传感器厂家批发,守护井盖安全

窨井盖广泛分布于城市街道&#xff0c;其管理效果直接反映了城市治理的现代化程度。根据住房和城乡建设部发布的《关于进一步加强城市窨井盖安全管理的通知》&#xff0c;全国各地需加强窨井盖的安全管理。作为市政基础设施的一个重要的组成部分&#xff0c;井盖的管理工作不仅…...

python命令行交互 引导用户选择宠物

字多不看&#xff0c;直接体验 代码 以下代码将在命令行中&#xff0c;引导用户选择一个或者多个宠物&#xff0c;并反馈用户选择的宠物 # -*- coding:UTF-8 -*- """ author: dyy contact: douyaoyuan126.com time: 2023/11/22 15:19 file: 在命令行中引导用户…...

Leetcode—167.两数之和 II - 输入有序数组【中等】

2023每日刷题&#xff08;四十一&#xff09; Leetcode—167.两数之和 II - 输入有序数组 实现代码 /*** Note: The returned array must be malloced, assume caller calls free().*/ int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {*returnSiz…...

MybatisPlus改造逻辑删除有多方便

MybatisPlus的逻辑删除可以有效保留历史数据。之前没有用逻辑删除的项目&#xff0c;想改造成逻辑删除总共需要几步&#xff1f; 答案&#xff1a;4步搞定 一、修改pom.xml的MybatisPlus版本&#xff08;注意版本兼容性&#xff09; <properties>...<!--<mybatis-…...

希尔伯特变换-matlab仿真

希尔伯特变换(hilbert transform)简介 在信号处理中我们常见的有傅里叶变换,用来分析频域信息,还有拉普拉斯变换和z变换,用于系统分析系统响应。短时傅里叶分析和小波分析用于时频分析。希尔伯特变换似乎听到的比较少。我因为最近在做信号幅度提取的时候看到可以用希尔伯…...

python字典的基本操作详解

Python字典是一种数据结构&#xff0c;它存储的是键值对&#xff08;key-value pair&#xff09;。在Python中&#xff0c;字典用于存储和组织数据&#xff0c;并且提供了快速查找和访问数据的方法。 以下是一些Python字典的基本操作&#xff1a; 创建字典&#xff1a; # 创…...

[ CSS ] 内容超出容器后 以...省略

内容超出容器后 以…省略 当前效果 代码 <template><div class"box">有志者&#xff0c;事竟成&#xff0c;破釜沉舟&#xff0c;百二秦关终属楚; 有心人&#xff0c;天不负&#xff0c;卧薪尝胆&#xff0c;三千越甲可吞吴</div> </templa…...

Java远程连接本地开源分布式搜索引擎ElasticSearch

文章目录 前言1. Windows 安装 Cpolar2. 创建Elasticsearch公网连接地址3. 远程连接Elasticsearch4. 设置固定二级子域名 前言 简单几步,结合Cpolar内网穿透工具实现Java远程连接操作本地Elasticsearch。 什么是elasticsearch&#xff1f;一个开源的分布式搜索引擎&#xff0…...

递归回溯剪枝-子集

LCR 079. 子集 - 力扣&#xff08;LeetCode&#xff09; 方法一 1. 决策树&#xff1a;对于决策树&#xff0c;思考的角度不同&#xff0c;画出的决策树也会不同&#xff0c;这道题可以从两个角度来画决策树。 2. 考虑全局变量的使用&#xff1a; 使用全局变量 List<List&…...

VC++、MFC中操作excel时,Rang和Rangs的区别是什么?

Rang 参考微软说明 作用 表示一个单元格、一行、一列、一个包含单个或若干连续单元格区域的选定单元格范围&#xff0c;或者一个三维区域。 说明 Range 的默认成员将不包含参数的调用转发至 Value 属性 如&#xff0c;someRange someOtherRange 等效于 someRange.Value …...

使用Rust开发小游戏

本文是对 使用 Rust 开发一个微型游戏【已完结】[1]的学习与记录. cargo new flappy 在Cargo.toml的[dependencies]下方增加: bracket-lib "~0.8.7" main.rs中: use bracket_lib::prelude::*;struct State {}impl GameState for State { fn tick(&mut self,…...

笔记二十一、使用路由search进行传递参数

21.1 父组件设置路由参数 <NavLink to{classify?param_A${this.state.name}&param_B${this.state.age}} className{this.activeStyle}>classify</NavLink> import React from "react"; import {NavLink, Outlet} from "react-router-dom"…...

python多线程和多进程

1.多线程 线程是程序执行的最小单位&#xff0c;一个进程至少有一个线程。 提高并发性。通过线程可方便有效地实现并发性。进程可创建多个线程来执行同一程序的不同部分。 进程之间不能共享内存&#xff0c;但线程之间共享内存非常容易。 Python 常用的多线程库有threading 和…...

VMware虚拟机网络配置详解

vmware为我们提供了三种网络工作模式&#xff0c;它们分别是&#xff1a;Bridged&#xff08;桥接模式&#xff09;、NAT&#xff08;网络地址转换模式&#xff09;、Host-Only&#xff08;仅主机模式&#xff09; 打开vmware虚拟机&#xff0c;我们可以在选项栏的“编辑”下的…...

VUE语法--img图片不显示/img的src动态赋值图片显示

1、问题概述 常见情景1&#xff1a;在VUE中使用img显示图片的时候&#xff0c;通过传参的方式传入图片的路径和名称&#xff0c;VUE不加载本地资源而是通过http://localhost:8080/...的地址去加载网络资源&#xff0c;从而出现了图片无法显示的情况。 常见情景2&#xff1a;针…...

springboot+vue智能企业设备管理系统05k50

智能设备管理系统主要是为了提高工作人员的工作效率和更方便快捷的满足用户&#xff0c;更好存储所有数据信息及快速方便的检索功能&#xff0c;对系统的各个模块是通过许多今天的发达系统做出合理的分析来确定考虑用户的可操作性&#xff0c;遵循开发的系统优化的原则&#xf…...

C++中的new、operator new与placement new

new operator new operator是我们常用的new。 new 和 delete 是用来在 堆上申请和释放空间的 &#xff0c;是 C 定义的 关键字&#xff0c;和 sizeof 一样。 实际 new / delete 和 malloc / free 最大的区别是&#xff0c;前者对于 自定义类型 除了可以开辟空间&#xff0c;…...

仅限奇点大会注册参会者获取的《多模态虚拟人性能基准测试套件v2.6》——现在下载还剩最后137个授权席位

第一章&#xff1a;2026奇点智能技术大会&#xff1a;多模态虚拟人 2026奇点智能技术大会(https://ml-summit.org) 核心突破&#xff1a;跨模态对齐与实时驱动 本届大会首次公开展示了端到端可训练的多模态虚拟人框架“SynthAvatar-X”&#xff0c;支持文本、语音、肢体动作与…...

Java 从入门到精通(十六):线程通信与 wait()/notify(),为什么有些线程不是抢锁,而是在“等条件”?

Java 从入门到精通&#xff08;十六&#xff09;&#xff1a;线程通信与 wait()/notify()&#xff0c;为什么有些线程不是抢锁&#xff0c;而是在“等条件”&#xff1f; 前一篇我们把线程同步这件事先讲透了&#xff1a;为什么多个线程一起改共享变量&#xff0c;结果会乱什么…...

Unity Asset Bundle文件结构拆解:用十六进制编辑器手把手分析Header与Block

Unity Asset Bundle二进制探秘&#xff1a;从十六进制视角解析文件结构与优化实践 当你在Unity中点击"Build AssetBundles"时&#xff0c;那个看似普通的.assetbundle文件内部究竟藏着怎样的秘密&#xff1f;作为从事Unity开发多年的技术顾问&#xff0c;我见过太多开…...

LeetCode 167. Two Sum II - Input Array Is Sorted 题解

LeetCode 167. Two Sum II - Input Array Is Sorted 题解 题目描述 给你一个下标从 1 开始的整数数组 numbers&#xff0c;该数组已按 非递减顺序排列&#xff0c;请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers…...

华硕笔记本性能调控终极方案:G-Helper轻量级工具完全指南

华硕笔记本性能调控终极方案&#xff1a;G-Helper轻量级工具完全指南 【免费下载链接】g-helper Lightweight, open-source control tool for ASUS laptops and ROG Ally. Manage performance modes, fans, GPU, battery, and RGB lighting across Zephyrus, Flow, TUF, Strix,…...

2025年知识竞赛软件评分排行榜权威解读

&#x1f3c6; 2025年知识竞赛软件评分排行榜权威解读多维评估 聚焦实用 选型指南&#x1f4ca; 排行榜综述&#xff1a;多维评估&#xff0c;聚焦实用随着数字化教育的深入与企业培训形式的创新&#xff0c;知识竞赛软件已成为激发学习动力、检验培训成果的重要工具。2025年…...

Draw.io零基础安装指南(含最新安装包资源)

1. Draw.io零基础安装指南 第一次接触Draw.io时&#xff0c;我也被它简洁的界面和强大的功能惊艳到了。作为一款完全免费的绘图工具&#xff0c;它不仅能画流程图、思维导图&#xff0c;还能制作专业的UML图和网络拓扑图。最让我惊喜的是&#xff0c;它的安装过程出奇地简单&am…...

limelight.vim 操作符映射:深入理解 <Plug> 映射机制

limelight.vim 操作符映射&#xff1a;深入理解 映射机制【免费下载链接】limelight.vim :flashlight: All the worlds indeed a stage and we are merely players 项目地址: https://gitcode.com/gh_mirrors/li/limelight.vim limelight.vim 是一款专为 Vim 用户设计的…...

重新定义开机瞬间:用HackBGRT打造个性启动画面

重新定义开机瞬间&#xff1a;用HackBGRT打造个性启动画面 【免费下载链接】HackBGRT Windows boot logo changer for UEFI systems 项目地址: https://gitcode.com/gh_mirrors/ha/HackBGRT 想象一下&#xff0c;每次按下电源键的瞬间&#xff0c;迎接你的不再是无趣的W…...

2026实战:C#上位机+YOLOv11实现智能安防管控,危险区域实时报警(附完整代码)

最近接了一个工厂智能安防项目,需求是实现人员闯入危险区域(如高压设备区、化工原料区)实时报警、人员计数统计,还要支持现场画面实时预览和报警记录追溯。一开始用传统的红外传感器方案,误报率高达30%,而且无法区分人员和杂物,根本满足不了需求。最终采用 C#上位机+YOL…...