數組中元素的第一個索引與最後一個索引之間的最大差  


難度級別 中烘焙
經常問 ol石 亞馬遜 遠足 我的旅行 奧拉出租車 SAP實驗室
排列 哈希

假設您有一個 排列 of 整數。 問題“數組中元素的第一個索引與最後一個索引之間的最大差”要求找出數組中存在的每個數字的第一個索引與最後一個索引之間的差,以使該差最大。

例  

arr[] =  {2, 3, 5, 1, 4, 6, 2, 5};
6

解釋

2的第一個索引→0

2的最后索引→6

最大差異(6-0)= 6

數組中元素的第一個索引與最後一個索引之間的最大差

arr[] =  {2, 3, 6, 5, 4, 5, 1, 4};
3

解釋

4的第一個索引→4

4的最后索引→7

最大差異(7-4)= 3

算法  

  1. 遍歷整個 排列.
  2. 選擇一個數組的每個元素,並獲取其第一個和最後一個元素,並將其存儲到HashTable中。
  3. 遍歷 地圖:
    1. 找出每個元素的第一個索引與最後一個索引之間的差異。
    2. 將最大差異存儲到某個變量中,並在發現最大值之前的值時繼續對其進行更新。
  4. 返回最大差。

解釋

我們得到了一個 整數 數組,我們需要找出數組每個值的第一個索引和最後一個索引之間的差異。 找出第一個索引與最後一個索引之間任何數字的最大差異。 為此,我們將使用 哈希。 我們將獲取一個數組元素,並找出其第一個索引和最後一個索引,或者何時首先出現和最後出現。

也可以看看
在數組中查找具有最大產品的對

將所有元素及其第一個和最後一個索引放入地圖後,遍歷地圖。 現在選擇每個元素,然後獲取它們的第一個索引和最後一個索引,然後找出差異,以使差異最大。 我們可以使用一個變量 最大差異 留意最大差異。 我們將使用一個類及其對象來存儲每個元素的第一個和最後一個索引。

讓我們考慮一個例子:

Arr [] = {2、3、5、1、4、6、2、5}

我們有一個數組輸入。 為了解決這個問題,我們將使用一個類。 如果是第一次遍歷每個元素,我們將為其尋找。 然後,我們將其索引存儲為第一個索引,並且當該相同元素再次出現時。 然後,每次我們將其索引存儲為第二個索引。 使用此方法,我們得到的地圖如下:

映射:1-> 3:null,

2-> 0:6,

3-> 1,為空,

4-> 4:null,

5-> 2:7,

6-> 5:空

我們將遍歷地圖,並獲取每個值並檢查其索引的差異。 我們將忽略所有具有空值的值。 所以我們有2和5,其中 2 第一個索引與最後一個索引之間的最大差(6)大於 5 兩者之間有差異(5)。 因此,我們將返回6作為最大差異,這將是我們的答案。

C ++代碼查找數組中元素的第一個索引與最後一個索引之間的最大差  

#include<bits/stdc++.h>

using namespace std;

int maxDifference(int arr[], int n)
{
    struct IndexValue
    {
        int fir, last;
    };
    unordered_map<int, IndexValue> MAP;
    for (int i=0; i<n; i++)
    {
        if (MAP.find(arr[i]) == MAP.end())
            MAP[arr[i]].fir = i;

        MAP[arr[i]].last = i;
    }

    int difference, differenceIndex = INT_MIN;

    unordered_map<int, IndexValue>::iterator itr;
    for (itr=MAP.begin(); itr != MAP.end(); itr++)
    {
        difference = (itr->second).last - (itr->second).fir;
        if (differenceIndex < difference)
            differenceIndex = difference;
    }
    return differenceIndex;
}
int main()
{
    int arr[] = {2, 3, 5, 1, 4, 6, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference b/w the first and last index of a number= "<<maxDifference(arr, n);
    return 0;
}
Maximum difference b/w the first and last index of a number= 6

Java代碼查找數組中元素的第一個索引與最後一個索引之間的最大差  

import java.util.HashMap;
import java.util.Map;

class IndexValue
{
    int first;
    int second;
    public IndexValue()
    {
        super();
    }
}
class DifferenceOfIndexes
{
    private static int getIndexesDifferent(int[] arr)
    {
        int n = arr.length;
        int differenceIndex = 0;
        Map<Integer, IndexValue> MAP = new HashMap<Integer, IndexValue>();

        for (int i = 0; i < n; i++)
        {
            if (MAP.containsKey(arr[i]))
            {
                IndexValue iv = MAP.get(arr[i]);
                iv.second = i;
            }
            else
            {
                IndexValue iv = new IndexValue();
                iv.first = i;
                MAP.put(arr[i], iv);
            }
        }
        for (Map.Entry<Integer, IndexValue> entry : MAP.entrySet())
        {
            IndexValue iv = entry.getValue();
            if ((iv.second - iv.first) > differenceIndex)
            {
                differenceIndex = iv.second - iv.first;
            }
        }
        return differenceIndex;
    }
    public static void main(String[] args)
    {
        int arr[]= {2,3,5,1,4,6,2,5};
        System.out.println("Maximum difference b/w the first and last index of a number= "+ getIndexesDifferent(arr));
    }
}
Maximum difference b/w the first and last index of a number= 6

複雜度分析  

時間複雜度

O(N) 哪裡 “ n' 是數組中元素的數量

也可以看看
從後綴到中綴的轉換

空間複雜度

O(N) 哪裡 “ n' 是數組中元素的數量