java查重精确算法_一个查重算法的多种实现思路

秒速五厘米 2022-11-06 10:54 165阅读 0赞

需求描述：已知一个长度为100的int型数组，并且每个元素的值大于等于1，并小于等于100，写出一个函数，判断该数组中是否存在重复元素。

这个是大概2年前参加面试的一道算法题，不算难，相信大家都有了自己的一个解法，但怎样才算具有最少时间复杂度和最小空间复杂度的解法呢？

class ArrayFindRepeat

\{

private int\[\] \_arr;

public ArrayFindRepeat(int\[\] arr)

\{

this.\_arr = arr;

\}

\}

方法一

///

/// 最普通的思路，把每个元素和数组本身遍历一次

///

///

public bool IsContainRepeat1()

\{

for (int i = 0; i < \_arr.Length; i++)

\{

for (int j = 0; j < \_arr.Length; j++)

\{

if (j != i) //排除依次循环的元素本身

\{

if (\_arr\[j\] == \_arr\[i\])

return true;

\}

\}

\}

return false;

\}

方法二

///

/// 先排序，再遍历每个元素

///

///

public bool IsContainRepeat2()

\{

var newArr = (from a in \_arr

orderby a ascending

select a).ToArray();

for (int i = 0; i < newArr.Length; i++)

\{

if (newArr\[i\] != i + 1)

return true;

\}

return false;

\}

方法三

///

/// 使用哈希表键不能重复的特性

///

///

public bool IsContainRepeat3()

\{

HashSet ht = new HashSet();

foreach (int i in \_arr)

\{

if (!ht.Add(i))

\{

return true;

\}

\}

return false;

\}

方法四

///

/// 满足条件的数组只有一种情况，就是1-100，使用临时数组，做标记位的方法

///

///

public bool IsContainRepeat4()

\{

int\[\] temp = new int\[\_arr.Length + 1\];

for (int i = 0; i < \_arr.Length; i++)

\{

int a = \_arr\[i\];

if (temp\[a\] != 0)

\{

return true;

\}

else

\{

temp\[a\] = 1;

\}

\}

return false;

\}

相信一定有更简单的解法，欢迎大家拍砖。

发表评论取消回复

表情：

评论列表（有 0 条评论，165人围观）

还没有评论，来说两句吧...

相关阅读

相关列表查重和去重

查重代码： List<String> list = Arrays.asList("123", "1234", "12345", "123456",

男娘i/ 2024年03月17日 22:59/ 0 赞/ 48 阅读

相关 MySql 查重、去重的实现

假设有一个表user，字段分别有id–nick\_name–password–email–phone，分情况如下（注意删除多余记录时要创建临时表，不然会报错）：一、单字段（

川长思鸟来/ 2024年01月20日 07:32/ 0 赞/ 14 阅读

相关 Java实现论文查重系统

1.论文查重系统背景日常生活中投票是非常常见的一件事，随着现在科技的发展，电子投票都是以线上操作的形势完成,本系统为模仿电子投票系统所作。 a.本系统有管理员登录，

忘是亡心i/ 2023年02月10日 13:26/ 0 赞/ 187 阅读

相关 Java算法——并查集

功能并查集是管理多个集合的算法，其功能包括集合的合并、集合内或集合间的查询。背景在中国古代，人们都比较重视血缘传承，几乎每家都至少会有一个男孩，后人总会牢记

川长思鸟来/ 2023年01月11日 09:07/ 0 赞/ 136 阅读

相关 java查重工具类_java文本查重工具类封装

【实例简介】终于重构好代码了，使用模式：模板模式、策略模式、建造者模式、单一职责，弄一个余弦定理、simhash文本查重代码，并使用二叉排序树和平衡二叉树(待测试)来优化查

旧城等待，/ 2022年11月10日 01:11/ 0 赞/ 142 阅读

相关 java查重精确算法_一个查重算法的多种实现思路

需求描述：已知一个长度为100的int型数组，并且每个元素的值大于等于1，并小于等于100，写出一个函数，判断该数组中是否存在重复元素。这个是大概2年前参加面试的一道算法题

秒速五厘米/ 2022年11月06日 10:54/ 0 赞/ 166 阅读

相关 555-大数据查重-位图算法

大数据查重-位图算法位：内存管理的最小单位是字节，一个字节是8个位。 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJ

ゝ一世哀愁。/ 2022年09月11日 06:20/ 0 赞/ 130 阅读

相关论文查重原理及实现

论文查重原理及实现原理: 在知网上的论文检测为整篇的进行上传但是本人却是提交自己的正式论文部分上去的(paperpass),

我不是女神ヾ/ 2022年06月15日 04:24/ 0 赞/ 202 阅读

相关 MySql数据查重、去重的实现

刚电话面试被问的，但是没有答出来，在此记录一下。原文：[https://blog.csdn.net/lzc4869/article/details/79128865][ht

青旅半醒/ 2022年02月25日 08:46/ 0 赞/ 243 阅读

相关 HDU - 4821 String hash算法 O(n)查重判斷

Time limit 1000 msMemory limit 32768 kB Given a string S and two integers L and M, w

快来打我*/ 2021年09月20日 12:50/ 0 赞/ 161 阅读