一道简单的数组遍历题,加上四个条件后感觉无从下手

2024-02-13 13:59

本文主要是介绍一道简单的数组遍历题,加上四个条件后感觉无从下手,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

640?wx_fmt=jpeg

作者 | P.yh

来源 | 五分钟学算法

今天分享的题目来源于 LeetCode 第 287 号问题:寻找重复数。

题目描述

给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

示例 1:

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

示例 2:

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

说明:

  • 不能更改原数组(假设数组是只读的)。

  • 只能使用额外的 O(1) 的空间。

  • 时间复杂度小于 O(n^2) 。

  • 数组中只有一个重复的数字,但它可能不止重复出现一次。

题目解析

题目的限制真多!!!

首先 不能改变数组 导致无法排序,也无法用 index 和元素建立关系;

只能使用 O(1) 的空间 意味着使用哈希表去计数这条路也走不通;

时间复杂度必须小于 O(n^2) 表示暴力求解也不行;

重复的元素可重复多次 这一条加上后,本来可以通过累加求和然后做差 sum(array) - sum(1,2,...,n) 的方式也变得不可行。

本来是非常简单的一道数组遍历的题目,加上了上面这四个条件后感觉有点无从下手

我们说做题要借助算法,而不是空想,因此对于这道题也不例外,我们可以问自己这样一个问题,就是 “什么样的算法可以不使用额外的空间解决数组上面的搜索问题?”

静静的思索一下。

你这时应该隐隐约约知道了,难道是 二分查找

什么?二分查找法?!

二分查找法不是对有序数组才适用么?

这里澄清一个误区,二分法的使用 并不一定 需要在排序好的数组上面进行,不要让常见的例题限制了你的思路,二分法还有一个比较高级的用法叫做 按值二分

这道题目交代的信息很少,我们只需要关注两个东西 - 数组,数组里的元素,利用二分我们需要去思考的是,我们要找符合条件的元素作为答案,那么 比答案小的元素具有什么样的特质,比答案大的元素又具有什么样的特质?,结合题目给我们的例子来看看:

( 说明:下面的  <=  符号表明 小于或者等于。)

例1:

[1,3,4,2,2]                      元素个数
<= 1 的元素:1                       1
<= 2 的元素:1, 2, 2                 3
<= 3 的元素:1, 2, 2, 3              4
<= 4 的元素:1, 2, 2, 3, 4           5

例2:

[3,1,3,4,2]
<= 1 的元素:1                        1
<= 2 的元素:1, 2                     2
<= 3 的元素:1, 2, 3, 3               4
<= 4 的元素:1, 2, 3, 3, 4            5

极端一点的例子 (必须保证数组的长度是 n + 1, 并且元素都在区间[1,n] 上, 有且只有一个重复)

[3,3,3,3,4]
<= 1 的元素:                        0
<= 2 的元素:                        0
<= 3 的元素:3, 3, 3, 3              4
<= 4 的元素:3, 3, 3, 3, 4           5

看完上面几个例子,相信你明白了一个事实:

  • “如果选中的数 小于 我们要找的答案,那么整个数组中小于或等于该数的元素个数必然小于或等于该元素的值;

  • 如果选中的数 大于或等于 我们要找的答案,那么整个数组中小于或等于该数的元素个数必然 大于 该元素的值”

而且你可以看到,我们要找的答案其实就处于一个分界点的位置,寻找边界值,这又是二分的一个应用,而且题目已经告诉我们数组里面的值只可能在 [1, n] 之间,这么一来,思路就是在 [1, n] 区间上做二分,然后按我们之前提到的逻辑去做分割。整个解法的时间复杂度是 O(nlogn),也是满足题目要求的。

上面的解法不是最优的,但是个人觉得是根据现有的知识比较容易想到的。

另外一种 O(n) 的解法借鉴快慢指针找交点的思想,算法非常的巧妙,也非常的有趣,但不太容易想到,这里把代码放上。

动画描述

代码实现一

//二分查找
class Solution {public int findDuplicate(int[] nums) {int len = nums.length;int start = 1;int end = len - 1;while (start < end) {int mid = start + (end - start) / 2;int counter = 0;for (int num:nums) {if (num <= mid) {counter++;}}if (counter > mid) {end = mid;} else {start = mid + 1;}}return start;}
}

代码实现二

//快慢指针
public int findDuplicate(int[] nums) {        int fast = nums[nums[0]];int slow = nums[0];while (fast != slow) {fast = nums[nums[fast]];slow = nums[slow];}slow = 0;while (fast != slow) {fast = nums[fast];slow = nums[slow];}return slow;
}

640?

有热门推荐?

1.【程序员】

2.【GitHub】

3.【算法】

4.【数据结构】

640?wx_fmt=jpeg

▼ 点击『阅读原文』解锁更多图解 LeetCode 题目

这篇关于一道简单的数组遍历题,加上四个条件后感觉无从下手的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/lyshark_lyshark/article/details/126792646
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/705718

相关文章

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

SQL中JOIN操作的条件使用总结与实践

《SQL中JOIN操作的条件使用总结与实践》在SQL查询中,JOIN操作是多表关联的核心工具,本文将从原理,场景和最佳实践三个方面总结JOIN条件的使用规则,希望可以帮助开发者精准控制查询逻辑... 目录一、ON与WHERE的本质区别二、场景化条件使用规则三、最佳实践建议1.优先使用ON条件2.WHERE用

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

基于Python实现一个简单的题库与在线考试系统

《基于Python实现一个简单的题库与在线考试系统》在当今信息化教育时代,在线学习与考试系统已成为教育技术领域的重要组成部分,本文就来介绍一下如何使用Python和PyQt5框架开发一个名为白泽题库系... 目录概述功能特点界面展示系统架构设计类结构图Excel题库填写格式模板题库题目填写格式表核心数据结构

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》:本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示

python进行while遍历的常见错误解析

《python进行while遍历的常见错误解析》在Python中选择合适的遍历方式需要综合考虑可读性、性能和具体需求,本文就来和大家讲解一下python中while遍历常见错误以及所有遍历方法的优缺点... 目录一、超出数组范围问题分析错误复现解决方法关键区别二、continue使用问题分析正确写法关键点三

windows和Linux安装Jmeter与简单使用方式

《windows和Linux安装Jmeter与简单使用方式》:本文主要介绍windows和Linux安装Jmeter与简单使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录Windows和linux安装Jmeter与简单使用一、下载安装包二、JDK安装1.windows设

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序