数组中最远的相等元素 [英] Farthest equal elements in an array

问题描述

假设您有一个未排序的数组，那么如何找到2个相等的元素，使它们在数组中最远。例如，对于 8 7 3 4 7 5 3 9 3 7 9 0 ，ans将为 7（9）-7（1）= 8 。
我想到了以下

  initialise max = 0 
使用散列，将元素与每当发生冲突时，将其索引
进行比较，将当前索引与带哈希值的一个
比较（如果较大），设置max =当前索引-哈希值一个，并将元素与索引一起复制到其他位置。 
  

运行时间-O（n）和空间-O（n）。它是否正确？有更好的解决方案。

解决方案

O（n）运行时间和O（n）空间似乎是最佳的AFAIK。 / p>

这里是python实现：

 ＃！/ usr / bin / python 
 hashindex = {} 
 
l = [8,7,3,4,7,5,3,9,3,7,9,0] 
 
 max_diff = 0 
值= 0 
 
对于范围内的i（len（l））：
索引= hashindex.get（l [i]，无）
如果索引：
 hashindex [l [i]] =（索引[0]，i）
否则：
 hashindex [l [i]] =（i，i）
 diff = hashindex [l [i]] [1]-hashindex [l [i]] [0] 
如果diff> max_diff：
 max_diff = diff 
 value = l [i] 
 
 print max_diff，值
  

Suppose you have an unsorted array, how will you find 2 equal elements such that they are the farthest in the array. For eg 8 7 3 4 7 5 3 9 3 7 9 0 the ans will be 7(9) - 7(1) = 8. I have thought of the following

initialise max = 0
using hashing, store the elements along with its index
whenever there is a collision, compare the current index with the hashed one
if it is greater, set max = current index - hashed one and copy element along with index to some other location.

runs in time - O(n) and space - O(n). Is this correct? Is there a better solution.

解决方案

O(n) running time and O(n) space seems to be optimal AFAIK.

Here's python implementation:

#!/usr/bin/python
hashindex = {}

l = [8,7,3,4,7,5,3,9,3,7,9,0]

max_diff = 0
value = 0

for i in range(len(l)):
    indices = hashindex.get(l[i], None)
    if indices:
        hashindex[l[i]] = (indices[0], i)
    else:
        hashindex[l[i]] = (i, i)
    diff = hashindex[l[i]][1] - hashindex[l[i]][0]
    if diff > max_diff:
        max_diff = diff
        value = l[i]

print max_diff, value

这篇关于数组中最远的相等元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！