blocks|key|797656|text|一种可能的解决方案是维护外部散列映射。迭代数组，并将找到的值的索引放入散列映射中。完成后，您现在知道哪个数字是重复的，以及找到它的位置的索引。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|797657|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

One possible solution is to maintain an external hash map. Iterate the array, and place the indices of values found into the hash map. When done, you now know which number was duplicated and the indices of the locations it was found at.

blocks|key|4189318|text|在面试的情况下，我想你有机会围绕这个问题提问，例如，有多少个数字？数字的范围是多少？您可以声明，最佳算法可能会根据不同而变化。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4189319|这给了你一个展示如何解决问题的机会。|4189320|如果数组中整数的范围足够小，那么可以创建另一个数组来记录找到每个整数的次数，然后线性遍历数组，累积出现次数，当出现次数为2时停止。|4189321|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

In an interview situation, I guess its your chance to ask around the question, for example, how many numbers? what range of numbers? you could state that an optimum algorithm could change depending. 

That gives you a chance to show how you solve problems.

If the range of ints in the array is small enough then you could create another array to keep count of the number of times each integer is found then go linearly through the array accumulating occurrence counts, stopping when you get to an occurance count of two.

blocks|key|4189241|text|Hash在这里会做得很好。一个接一个地添加数字，每次检查数字是否已经存在。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4189242|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Hash will do just fine in here. Add numbers to it one by one, each time checking if number's already in there.

blocks|key|408028|text|好吧，可能有一些技巧(通常是)。但是即兴的，您应该能够对列表进行排序(O(nlogn))。然后，只需找到一个与下一个相同的数字(线性搜索-+O(n))。当然，您必须将其排序为值和原始索引的元组，这样才能返回您正在查找的索引。但重点是，完成这项工作的算法的上限应该是O(nlogn)。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|408029|如果您只是线性地遍历列表，您可以获取每个索引，然后在列表的其余部分中搜索匹配的索引。我认为这大致等同于在冒泡排序中所做的工作，所以它可能是O(n%5E2)，但很简单。|408030|我真的很讨厌像面试问题这样的诡计问题。它们有点像视觉错觉:要么你看到了，要么没有，但如果你看不到诀窍，它并不会真正说明你有什么不好的。|408031|entityMap^0|Z|8|1Y|4|3O|8|0|1X|6|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@$9|M|A|N|B|C]|$9|O|A|P|B|C]|$9|Q|A|R|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|S|8|@$9|T|A|U|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|V|8|@]|D|@]|E|$]]|$1|J|3|-4|5|6|7|W|8|@]|D|@]|E|$]]]|K|$]]

Well, there probably is some trick (usually is). But just off the cuff, you should be able to sort the list (<code>O(nlogn)</code>). Then its just a matter of finding a number that is the same as the next one (linear search - <code>O(n)</code>). You'd have to sort it as tuples of values and original indices of course, so you could return that index you are looking for. But the point is that the upper bound on an algorithim that will do the job should be <code>O(nlogn)</code>.

If you just go through the list linerally, you could take each index, then search through the rest of the list after it for a matching index. I think that's roughly equivalent to the work done in a bubble sort, so it would probably be <code>O(n^2)</code>, but a simple one.

I really hate trick questions as interview questions. They are kind of like optical illusions: Either you see it or you don't, but it doesn't really say anything bad about you if you don't see the trick.

blocks|key|408048|text|我会试试这个：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|408049|在知道重复的elm之前，立即将重复元素的位置/索引存储在hash/dictionary|408050|as中，存储其第一个位置(来自散列)和结果数组中的当前位置|unordered-list-item|408051|
|408052|408053|408054|将进一步的列表中的elm与重复的elm进行比较，将找到的位置附加到结果数组|408055|408056|在代码中：|408057|Function+locRep(+aSrc+)
++'+to+find+repeated+elm+quickly
++Dim+dicElms+:+Set+dicElms+=+CreateObject(+"Scripting.Dictionary"+)
++'+to+store+the+locations
++Dim+aLocs+++:+aLocs+++++++=+Array()
++'+once+found,+simple+comparison+is+enough
++Dim+vRepElm+:+vRepElm+++++=+Empty
++Dim+nIdx
++For+nIdx+=+0+To+UBound(+aSrc+)
++++++If+vRepElm+=+aSrc(+nIdx+)+Then+'+repeated+elm+known,+just+store+location
+++++++++ReDim+Preserve+aLocs(+UBound(+aLocs+)+%2B+1+)
+++++++++aLocs(+UBound(+aLocs+)+)+=+nIdx
++++++Else+'+repeated+elm+not+known
+++++++++If+dicElms.Exists(+aSrc(+nIdx+)+)+Then+'+found+it
++++++++++++vRepElm+=+aSrc(+nIdx+)
++++++++++++ReDim+aLocs(+UBound(+aLocs+)+%2B+2+)
++++++++++++'+location+of+first+occurrence
++++++++++++aLocs(+UBound(+aLocs+)+-+1+)+=+dicElms(+aSrc(+nIdx+)+)
++++++++++++'+location+of+this+occurrence
++++++++++++aLocs(+UBound(+aLocs+)+++++)+=+nIdx
+++++++++Else
++++++++++++'+location+of+first+occurrence
++++++++++++dicElms(+aSrc(+nIdx+)+)+=+nIdx
+++++++++End+If
++++++End+If
++Next
++locRep+=+aLocs
End+Function|code-block|syntax|javascript|408058|测试运行：|408059|-------------------------------------------------
+++++0+1+2+3+4+5+6+7+8+9+0+1+2+3+4+5+6+7+8+9+0
Src:+1+3+6+4+7+6+9+2+6+6+6+6+8
Res:+2+5+8+9+10+11
ok

Src:
Res:
ok

Src:+1+2+3
Res:
ok

Src:+1+1+2+3+4+5+6
Res:+0+1
ok

Src:+1+2+3+4+5+6+6
Res:+5+6
ok

=================================================|408060|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|11|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|12|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|13|8|@]|9|@]|A|$]]|$1|I|3|-4|5|F|7|14|8|@]|9|@]|A|$]]|$1|J|3|H|5|6|7|15|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|16|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|17|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|18|8|@]|9|@]|A|$]]|$1|P|3|Q|5|R|7|19|8|@]|9|@]|A|$S|T]]|$1|U|3|V|5|6|7|1A|8|@]|9|@]|A|$]]|$1|W|3|X|5|R|7|1B|8|@]|9|@]|A|$S|T]]|$1|Y|3|-4|5|6|7|1C|8|@]|9|@]|A|$]]]|Z|$]]

I'd try this:

<ol>
<li>all elms of list have to be looked at (=> loop over the list)</li>
<li>before the repeated elm is known, store elm => location/index in a hash/dictionary</li>
<li>as soon as the second occurence of the repeated element is found, store its first postion (from the hash) and the current position in the result array</li>
<li>compare further elms of list against the repeated elm, append found locations to the result array</li>
</ol>

in code:

<pre><code>Function locRep( aSrc )
 ' to find repeated elm quickly
 Dim dicElms : Set dicElms = CreateObject( "Scripting.Dictionary" )
 ' to store the locations
 Dim aLocs : aLocs = Array()
 ' once found, simple comparison is enough
 Dim vRepElm : vRepElm = Empty
 Dim nIdx
 For nIdx = 0 To UBound( aSrc )
 If vRepElm = aSrc( nIdx ) Then ' repeated elm known, just store location
 ReDim Preserve aLocs( UBound( aLocs ) + 1 )
 aLocs( UBound( aLocs ) ) = nIdx
 Else ' repeated elm not known
 If dicElms.Exists( aSrc( nIdx ) ) Then ' found it
 vRepElm = aSrc( nIdx )
 ReDim aLocs( UBound( aLocs ) + 2 )
 ' location of first occurrence
 aLocs( UBound( aLocs ) - 1 ) = dicElms( aSrc( nIdx ) )
 ' location of this occurrence
 aLocs( UBound( aLocs ) ) = nIdx
 Else
 ' location of first occurrence
 dicElms( aSrc( nIdx ) ) = nIdx
 End If
 End If
 Next
 locRep = aLocs
End Function
</code></pre>

Test run:

<pre><code>-------------------------------------------------
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
Src: 1 3 6 4 7 6 9 2 6 6 6 6 8
Res: 2 5 8 9 10 11
ok

Src:
Res:
ok

Src: 1 2 3
Res:
ok

Src: 1 1 2 3 4 5 6
Res: 0 1
ok

Src: 1 2 3 4 5 6 6
Res: 5 6
ok

=================================================
</code></pre>

blocks|key|4189299|text|using+namespace+std;
list<int>+find_duplicate_idx(const+vector<int>&+A)
{
hash_map<int,+int>+X;
list<int>+idx;
for+(+int+i+=+0;+i+<+A.size();+%2B%2B+i+)+{
++hash_map<int,+int>::iterator+it+=+X.find(A[i]);
++if+(+it+!=+X.end()+)+{
++++idx.push_back(it->second);
++++idx.push_back(i);
++++for+(+int+j+=+i+%2B+1;+j+<+A.size();+%2B%2Bj+)
++++++if+(+A[j]+==+A[i]+)
++++++++idx.push_back(j);++
++++return+idx;
++}
++X[A[i]]+=+i;
}
return+idx;
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|4189300|这是我朋友提供的一个解决方案。感谢来自mitbbs.com的SETI|unstyled|4189301|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|J|8|@]|9|@]|A|$]]|$1|G|3|-4|5|F|7|K|8|@]|9|@]|A|$]]]|H|$]]

<pre><code>using namespace std;
list&lt;int&gt; find_duplicate_idx(const vector&lt;int&gt;&amp; A)
{
hash_map&lt;int, int&gt; X;
list&lt;int&gt; idx;
for ( int i = 0; i &lt; A.size(); ++ i ) {
 hash_map&lt;int, int&gt;::iterator it = X.find(A[i]);
 if ( it != X.end() ) {
 idx.push_back(it-&gt;second);
 idx.push_back(i);
 for ( int j = i + 1; j &lt; A.size(); ++j )
 if ( A[j] == A[i] )
 idx.push_back(j); 
 return idx;
 }
 X[A[i]] = i;
}
return idx;
}
</code></pre>

This is a solution my friend provided. Thank you SETI from mitbbs.com

blocks|key|4189343|text|使用散列映射来解决这个问题：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4189344|private+int+getRepeatedElementIndex(int[]+arr)+{

++++Map<Integer,+Integer>+map+=+new+HashMap();
++++//+find+the+duplicate+element+in+an+array
++++for+(int+i+=+0;+i+<+arr.length;+i%2B%2B)+{
++++++++if(map.containsKey(arr[i]))+{
++++++++++++return+i;
++++++++}+else+{
++++++++++++map.put(arr[i],+i);
++++++++}
++++}
++++throw+new+RuntimeException("No+repeated+element+found");
}|code-block|syntax|javascript|4189345|时间复杂度:+O(n)|4189346|空间复杂度:+O(n)|4189347|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

Use the hash-map to solve it :

<pre><code>private int getRepeatedElementIndex(int[] arr) {

 Map&lt;Integer, Integer&gt; map = new HashMap();
 // find the duplicate element in an array
 for (int i = 0; i &lt; arr.length; i++) {
 if(map.containsKey(arr[i])) {
 return i;
 } else {
 map.put(arr[i], i);
 }
 }
 throw new RuntimeException("No repeated element found");
}
</code></pre>

Time complexity : O(n)

Space complexity : O(n)

Consider array of <code>INT</code> of positive numbers:

<pre><code> {1,3,6,4,7,6,9,2,6,6,6,6,8}
</code></pre>

Given: only one number is repeated, return number and positions with efficient algorithm.

Any ideas for efficient algorithms?

Find repeated element in array

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

考虑正数的INT数组：    {1,3,6,4,7,6,9,2,6,6,6,6,8}给定:只有一个数字重复，用高效算法返回数字和位置。对高效的算法有什么想法吗？

问查找数组中的重复元素
EN

回答 7

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问查找数组中的重复元素EN

回答 7

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问查找数组中的重复元素
EN