数组中相同元素的两次出现之间的最大距离


难度级别 中等
经常问 德里韦里 事实集 狂徒 风筝
排列 哈希

假设给你一个 排列 与一些重复的数字。 我们必须找到数组中存在的两个具有不同索引的数字的相同出现之间的最大距离。

使用案列

输入:

数组= [1、2、3、6、2、7]

输出:

3

说明:

因为数组[1]和数组[4]的元素具有与'2'相同的元素,最大距离为3。

输入:

数组= [3、4、6、7、4、8、9、3]

输出:

7

说明:

因为元素数组[0]和数组[7]具有与'3'相同的元素,且最大距离为3。

两次出现相同元素之间的最大距离的算法

  1. 声明一个 地图.
  2. “ maxDistance” 到0。
  3. 当i小于数组的长度(n)时。
    1. 检查每个数组元素是否在地图中首次出现(如果是第一次出现),
      1. 然后将元素及其索引放入地图中。
    2. 其他(如果已经存在)
      1. 找出上一个和下一个之间的最大距离(索引之间的距离)。
      2. 将最大距离存储到 “ maxDistance”.
  4. 返回 “ maxDistance”.

说明

我们给出了一个包含一些重复元素的数组。 我们的任务是找出相同数字出现位置之间的最大差异。 我们将为此使用地图。 在该图中,我们将把数组元素作为键,并将它们的索引作为值。 然后,我们将找到相同编号的两个索引之间的最大差异或距离(如果存在),尽管我们需要找到相同元素之间的距离。

在映射中,每个键中都有一些值作为数组的元素及其索引,如果为每个元素找到两个索引,则我们将查找这些索引之间的差异,并找到前一个索引之间的较大差异 “ maxDistance” 还有现在的然后在遍历整个数组后,我们得到最大的最大距离。

让我们考虑一个例子:

使用案列

arr [] = {8、1、3、2、4、1、3、6、7、3、1};

i = 0,arr [i] = 8 => myMap = {8:0}

i = 1,arr [i] = 1 => myMap = {8:0,1:1}

i = 2,arr [i] = 3 => myMap = {8:0,1:1,3:2}

i = 3,arr [i] = 2 => myMap = {8:0,1:1,3:2,2:3}

i = 4,arr [i] = 4 => myMap = {8:0,1:1,3:2,2:3,4:4}

i = 5,arr [i] = 1 => myMap = {8:0,1:1,3:2,2:3,4:4},在这里它将找到当前索引和上一个索引之间的差异'1',(5-1 = 4),4存储在maxDistance中。

i = 6,arr [i] = 3 => myMap = {8:0,1:1,3:2,2:3,4:4}在这里,它将找到当前索引与'的先前索引之间的差异3',(6-2 = 4),但是4已经在maxDistance中了,所以没关系。

i = 7,arr [i] = 6 => myMap = {8:0,1:1,3:2,2:3,4:4,6:7}

i = 8,arr [i] = 7 => myMap = {8:0,1:1,3:2,2:3,4:4,6:7,7:8}

i = 9,arr [i] = 3 => myMap = {8:0,1:1,3:2,2:3,4:4,6:7,7:8}当前索引和上一个索引“ 3”(9-3 = 6),6存储在maxDistance中。

i = 10,arr [i] = 3 => myMap = {8:0,1:1,3:2,2:3,4:4,6:7,7:8}当前索引和上一个索引“ 1”(10-1 = 9),9存储在maxDistance中。

然后我们将maxDistance返回为9。

实施

C ++程序,用于数组中相同元素的两次出现之间的最大距离

#include<bits/stdc++.h>
using namespace std;

int getDistance(int arr[], int n)
{
    unordered_map<int, int> my_map;
    int maxDistance = 0;
    for (int i=0; i<n; i++)
    {
        if (my_map.find(arr[i]) == my_map.end())
            my_map[arr[i]] = i;
        else
            maxDistance = max(maxDistance, i - my_map[arr[i]]);
    }

    return maxDistance;
}
int main()
{
    int arr[] = {8, 1, 3, 2, 4, 1, 3, 6, 7, 3, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getDistance(arr, n);
    return 0;
}
9

Java程序,用于数组中相同元素的两次出现之间的最大距离

import java.io.*;
import java.util.*;

class distanceBSameNumbers
{
    static int getDistance(int[] arr, int n)
    {
        HashMap<Integer,Integer> my_map = new HashMap<>();

        int maxDistance = 0;

        for (int i = 0; i < n; i++)
        {
            if (!my_map.containsKey(arr[i]))
                my_map.put(arr[i], i);

            else
                maxDistance = Math.max(maxDistance, i - my_map.get(arr[i]));
        }

        return maxDistance;
    }
    public static void main(String args[])
    {
        int arr[] = {8,1,3,2,4,1,3,6,7,3,1};
        int n = arr.length;
        System.out.println(getDistance(arr, n));
    }
}
9

数组中相同元素的两次出现之间最大距离的复杂度分析

时间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。