剑指offer03:数组中重复的数组---leetcode:LCR 120. 寻找文件副本

2024-04-15 23:44

本文主要是介绍剑指offer03:数组中重复的数组---leetcode:LCR 120. 寻找文件副本,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

设备中存有 n 个文件,文件 id 记于数组 documents。若文件 id 相同,则定义为该文件存在副本。请返回任一存在副本的文件 id

示例 1:

输入:documents = [2, 5, 3, 0, 5, 0]
输出:0 或 5

提示:

  • 0 ≤ documents[i] ≤ n-1
  • 2 <= n <= 100000

思路,排序之后再看,原本以为是要返回重复的数组,打算用一个空数组做标记,结果只需返回一个重复的即可。

使用排序后的数组,找挨着的两个即可。排序的时间复杂度是O(nlogn),而找到重复元素的时间复杂度是O(n)。

int compare(const void* a,const void* b){return *(int*)a-*(int*)b;
}
int findRepeatDocument(int* documents, int documentsSize) {qsort(documents,documentsSize,sizeof(int),compare);for(int i=0;i<documentsSize-1;i++){int j=1;if(documents[i]==documents[i+j]){return documents[i];}}return 0;
}

使用哈希,使用数组中的值作为下标,进行标记。防止数组中值溢出,使用取余的办法。

int findRepeatDocument(int* documents, int documentsSize){int* hash=(int*)malloc(documentsSize*sizeof(int));for (int i = 0; i < documentsSize; i++) {hash[i] =-1;}for(int i = 0; i < documentsSize; i++){int p=documents[i]%documentsSize;if(hash[p]!=-1){return documents[i];}hash[documents[i]%documentsSize]=documents[i];}return 0;
}

这篇关于剑指offer03:数组中重复的数组---leetcode:LCR 120. 寻找文件副本的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

Oracle数据库使用 listagg去重删除重复数据的方法汇总

《Oracle数据库使用listagg去重删除重复数据的方法汇总》文章介绍了在Oracle数据库中使用LISTAGG和XMLAGG函数进行字符串聚合并去重的方法,包括去重聚合、使用XML解析和CLO... 目录案例表第一种:使用wm_concat() + distinct去重聚合第二种:使用listagg,

MySQL中删除重复数据SQL的三种写法

《MySQL中删除重复数据SQL的三种写法》:本文主要介绍MySQL中删除重复数据SQL的三种写法,文中通过代码示例讲解的非常详细,对大家的学习或工作有一定的帮助,需要的朋友可以参考下... 目录方法一:使用 left join + 子查询删除重复数据(推荐)方法二:创建临时表(需分多步执行,逻辑清晰,但会

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2

vue如何监听对象或者数组某个属性的变化详解

《vue如何监听对象或者数组某个属性的变化详解》这篇文章主要给大家介绍了关于vue如何监听对象或者数组某个属性的变化,在Vue.js中可以通过watch监听属性变化并动态修改其他属性的值,watch通... 目录前言用watch监听深度监听使用计算属性watch和计算属性的区别在vue 3中使用watchE

哈希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

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

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.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while