LeetCode第五天(442. 数组中重复的数据)

2024-03-28 02:12

本文主要是介绍LeetCode第五天(442. 数组中重复的数据),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

给你一个长度为 n 的整数数组 nums ,其中 nums 的所有整数都在范围 [1, n] 内,且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数,并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

class Solution {public List<Integer> findDuplicates(int[] nums) {//思路:遍历数组,每个数-1再取模,找出真实位置,再加上数组的长度,放进数组真实的位置上//再遍历,发现数组中元素大于2倍数组长度时,将其下标+1添加进返回结果的数组int len = nums.length;for(int num : nums){//找出真实位置int x = (num - 1) % len;//加上数组长度nums[x] += len; }//创建返回结果的数组List<Integer> ret = new ArrayList<Integer>();//遍历数组,找出数组中元素大于2倍数组长度的值for(int i = 0;i < len;i++){if(nums[i] > len * 2){ret.add(i+1);}}return ret;}
}

官解:

方法一:将元素交换到对应的位置
思路与算法

由于给定的 n个数都在 [1,n]的范围内,如果有数字出现了两次,就意味着 [1,n] 中有数字没有出现过。

因此,我们可以尝试将每一个数放在对应的位置。由于数组的下标范围是 [0,n−1],我们需要将数 i 放在数组中下标为 i−1 的位置:

如果 i 恰好出现了一次,那么将 iii 放在数组中下标为 i−1 的位置即可;
如果 i 出现了两次,那么我们希望其中的一个 i 放在数组下标中为 i−1 的位置,另一个 i 放置在任意「不冲突」的位置 j。也就是说,数 j+1 没有在数组中出现过。
这样一来,如果我们按照上述的规则放置每一个数,那么我们只需要对数组进行一次遍历。当遍历到位置 i时,如果 nums[i]−1≠i,说明 nums[i]出现了两次(另一次出现在位置 num[i]−1),我们就可以将 num[i]\textit{num}[i]num[i] 放入答案。

放置的方法也很直观:我们对数组进行一次遍历。当遍历到位置 iii 时,我们知道 nums[i]应该被放在位置 nums[i]−1。因此我们交换 num[i]和 nums[nums[i]−1] 即可,直到待交换的两个元素相等为止。

class Solution {public List<Integer> findDuplicates(int[] nums) {int n = nums.length;for (int i = 0; i < n; ++i) {while (nums[i] != nums[nums[i] - 1]) {swap(nums, i, nums[i] - 1);}}List<Integer> ans = new ArrayList<Integer>();for (int i = 0; i < n; ++i) {if (nums[i] - 1 != i) {ans.add(nums[i]);}}return ans;}public void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

方法二:使用正负号作为标记
思路与算法

我们也可以给 nums[i]加上「负号」表示数 i+1已经出现过一次。具体地,我们首先对数组进行一次遍历。当遍历到位置 iii 时,我们考虑 nums[nums[i]−1]的正负性:

如果 nums[nums[i]−1] 是正数,说明 nums[i]还没有出现过,我们将 nums[nums[i]−1] 加上负号;

如果 nums[nums[i]−1]是负数,说明 nums[i]已经出现过一次,我们将 nums[i]放入答案。

细节

由于 nums[i] 本身可能已经为负数,因此在将nums[i] 作为下标或者放入答案时,需要取绝对值。

class Solution {public List<Integer> findDuplicates(int[] nums) {int n = nums.length;List<Integer> ans = new ArrayList<Integer>();for (int i = 0; i < n; ++i) {int x = Math.abs(nums[i]);if (nums[x - 1] > 0) {nums[x - 1] = -nums[x - 1];} else {ans.add(x);}}return ans;}
}

这篇关于LeetCode第五天(442. 数组中重复的数据)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/854143

相关文章

大模型研发全揭秘:客服工单数据标注的完整攻略

在人工智能(AI)领域,数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者,掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中,工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注,不仅能够帮助提升客服自动化系统的智能化水平,还能优化客户服务流程,提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

基于MySQL Binlog的Elasticsearch数据同步实践

一、为什么要做 随着马蜂窝的逐渐发展,我们的业务数据越来越多,单纯使用 MySQL 已经不能满足我们的数据查询需求,例如对于商品、订单等数据的多维度检索。 使用 Elasticsearch 存储业务数据可以很好的解决我们业务中的搜索需求。而数据进行异构存储后,随之而来的就是数据同步的问题。 二、现有方法及问题 对于数据同步,我们目前的解决方案是建立数据中间表。把需要检索的业务数据,统一放到一张M

关于数据埋点,你需要了解这些基本知识

产品汪每天都在和数据打交道,你知道数据来自哪里吗? 移动app端内的用户行为数据大多来自埋点,了解一些埋点知识,能和数据分析师、技术侃大山,参与到前期的数据采集,更重要是让最终的埋点数据能为我所用,否则可怜巴巴等上几个月是常有的事。   埋点类型 根据埋点方式,可以区分为: 手动埋点半自动埋点全自动埋点 秉承“任何事物都有两面性”的道理:自动程度高的,能解决通用统计,便于统一化管理,但个性化定

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

异构存储(冷热数据分离)

异构存储主要解决不同的数据,存储在不同类型的硬盘中,达到最佳性能的问题。 异构存储Shell操作 (1)查看当前有哪些存储策略可以用 [lytfly@hadoop102 hadoop-3.1.4]$ hdfs storagepolicies -listPolicies (2)为指定路径(数据存储目录)设置指定的存储策略 hdfs storagepolicies -setStoragePo

Hadoop集群数据均衡之磁盘间数据均衡

生产环境,由于硬盘空间不足,往往需要增加一块硬盘。刚加载的硬盘没有数据时,可以执行磁盘数据均衡命令。(Hadoop3.x新特性) plan后面带的节点的名字必须是已经存在的,并且是需要均衡的节点。 如果节点不存在,会报如下错误: 如果节点只有一个硬盘的话,不会创建均衡计划: (1)生成均衡计划 hdfs diskbalancer -plan hadoop102 (2)执行均衡计划 hd

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.