数组中元素的第一个索引和最后一个索引之间的最大差异-yiteyi-C++库

给定一个由n个整数组成的数组。其任务是找出每个不同元素的第一个和最后一个索引的差异，以便最大化差异。例如：

null

Input : {2, 1, 3, 4, 2, 1, 5, 1, 7}Output : 6Element 1 has its first index = 1and last index = 7Difference = 7 - 1 = 6Other elements have a smaller first and lastindex differenceInput : {2, 2, 1, 1, 8, 8, 3, 5, 3} Output : 2Maximum difference is for indexes of element 3.

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 简单方法 就是运行两个循环，找出每个元素的差异，并相应地更新 最大差异 .它的时间复杂度为O（n ^2. )该方法还需要跟踪已访问的元素，以便不必要地计算它们的差异。一 有效的方法 使用哈希。它有以下步骤。

从左向右遍历输入数组。
对于每个不同的元素，映射其在哈希表中的第一个和最后一个索引。
遍历哈希表并计算每个元素的第一个和最后一个索引差。
相应地更新 最大差异 .

在下面的实现中无序地图已用于哈希，因为整数的范围未知。

C++

                         // C++ implementation to find the maximum difference                       
                         // of first and last index of array elements                       
                         #include <bits/stdc++.h>                       
           
                         using                                     namespace                                     std;                       
           
                         // function to find the                       
                         // maximum difference                       
                         int                                     maxDifference(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // structure to store first and last                       
                                                 // index of each distinct element                       
                                                 struct                                     index                       
                                                 {                       
                                                 int                                     f, l;                       
                                                 };                       
                                   
                                                 // maps each element to its                       
                                                 // 'index' structure                       
                                                 unordered_map<                                     int                                     , index> um;                       
                                   
                                                 for                                     (                                     int                                     i=0; i<n; i++)                       
                                                 {                       
                                                 // storing first index                       
                                                 if                                     (um.find(arr[i]) == um.end())                       
                                                 um[arr[i]].f = i;                       
                                   
                                                 // storing last index                       
                                                 um[arr[i]].l = i;                       
                                                 }                       
                                   
                                                 int                                     diff, max_diff = INT_MIN;                       
                                   
                                                 unordered_map<                                     int                                     , index>::iterator itr;                       
           
                                                 // traversing 'um'                       
                                                 for                                     (itr=um.begin(); itr != um.end(); itr++)                       
                                                 {                       
                                                 // difference of last and first index                       
                                                 // of each element                       
                                                 diff = (itr->second).l - (itr->second).f;                       
                                   
                                                 // update 'max_dff'                       
                                                 if                                     (max_diff < diff)                       
                                                 max_diff = diff;                       
                                                 }                       
                                   
                                                 // required maximum difference                       
                                                 return                                     max_diff;                       
                         }                       
           
           
                         // Driver program to test above                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {2, 1, 3, 4, 2, 1, 5, 1, 7};                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 cout <<                                     "Maximum Difference = "                       
                                                 <<maxDifference(arr, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java implementation to find the maximum difference                       
                         // of first and last index of array elements                       
                         import                                     java.util.HashMap;                       
                         import                                     java.util.Map;                       
           
                         public                                     class                                     MaxDiffIndexHashing {                       
           
                                                 static                                     class                                     Element {                       
                                                 int                                     first;                       
                                                 int                                     second;                       
           
                                                 public                                     Element() {                       
                                                 super                                     ();                       
                                                 }                       
           
                                                 public                                     Element(                                     int                                     first,                                     int                                     second) {                       
                                                 super                                     ();                       
                                                 this                                     .first = first;                       
                                                 this                                     .second = second;                       
                                                 }                       
                                                 }                       
           
                                                 public                                     static                                     void                                     main(String[] args) {                       
           
                                                 int                                     arr[]={                                     2                                     ,                                     1                                     ,                                     3                                     ,                                     4                                     ,                                     2                                     ,                                     1                                     ,                                     5                                     ,                                     1                                     ,                                     7                                     };                       
                                                 System.out.println(                                     "Maximum Difference= "                                     + maxDiffIndices(arr));                       
                                                 }                       
           
                                                 private                                     static                                     int                                     maxDiffIndices(                                     int                                     [] arr) {                       
                                                 int                                     n = arr.length;                       
                                                 int                                     maxDiffIndex =                                     0                                     ;                       
                                                 Map<Integer, Element> map =                                     new                                     HashMap<Integer, Element>();                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
                                                 if                                     (map.containsKey(arr[i])) {                       
                                                 Element e = map.get(arr[i]);                       
                                                 e.second = i;                       
                                                 }                                     else                                     {                       
                                                 Element e =                                     new                                     Element();                       
                                                 e.first = i;                       
                                                 map.put(arr[i], e);                       
                                                 }                       
           
                                                 }                       
           
                                                 for                                     (Map.Entry<Integer, Element> entry : map.entrySet()) {                       
                                                 Element e = entry.getValue();                       
                                                 if                                     ((e.second - e.first) > maxDiffIndex)                       
                                                 maxDiffIndex = e.second - e.first;                       
                                                 }                       
           
                                                 return                                     maxDiffIndex;                       
                                                 }                       
           
                         }                       

C#

                         // C# implementation to find the maximum difference                       
                         // of first and last index of array elements                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         public                                     class                                     MaxDiffIndexHashing                       
                         {                       
           
                                                 class                                     Element {                       
                                                 public                                     int                                     first;                       
                                                 public                                     int                                     second;                       
           
                                                 public                                     Element() {                       
                                                 }                       
           
                                                 public                                     Element(                                     int                                     first,                                     int                                     second) {                       
                                                 this                                     .first = first;                       
                                                 this                                     .second = second;                       
                                                 }                       
                                                 }                       
           
                                                 public                                     static                                     void                                     Main(String[] args) {                       
           
                                                 int                                     []arr={2, 1, 3, 4, 2, 1, 5, 1, 7};                       
                                                 Console.WriteLine(                                     "Maximum Difference= "                                     + maxDiffIndices(arr));                       
                                                 }                       
           
                                                 private                                     static                                     int                                     maxDiffIndices(                                     int                                     [] arr) {                       
                                                 int                                     n = arr.Length;                       
                                                 int                                     maxDiffIndex = 0;                       
                                                 Dictionary<                                     int                                     , Element> map =                                     new                                     Dictionary<                                     int                                     , Element>();                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 if                                     (map.ContainsKey(arr[i])) {                       
                                                 Element e = map[arr[i]];                       
                                                 e.second = i;                       
                                                 }                                     else                                     {                       
                                                 Element e =                                     new                                     Element();                       
                                                 e.first = i;                       
                                                 map.Add(arr[i], e);                       
                                                 }                       
           
                                                 }                       
           
                                                 foreach                                     (KeyValuePair<                                     int                                     , Element> entry                                     in                                     map) {                       
                                                 Element e = entry.Value;                       
                                                 if                                     ((e.second - e.first) > maxDiffIndex)                       
                                                 maxDiffIndex = e.second - e.first;                       
                                                 }                       
           
                                                 return                                     maxDiffIndex;                       
                                                 }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

Javascript

                         <script>                       
           
                         // JavaScript implementation to find the maximum difference                       
                         // of first and last index of array elements                       
           
                         // function to find the                       
                         // maximum difference                       
                         function                                     maxDifference(arr, n)                       
                         {                       
           
                                                 // structure to store first and last                       
                                                 // index of each distinct element                       
                                                 class index                       
                                                 {                       
           
                                                 constructor(f,l){                       
                                                 this                                     .f = f;                       
                                                 this                                     .l = l;                       
                                                 }                       
                                                 };                       
                                   
                                                 // maps each element to its                       
                                                 // 'index' structure                       
                                                 let um =                                     new                                     Map();                       
                                   
                                                 for                                     (let i=0; i<n; i++)                       
                                                 {                       
                                                 // storing last index                       
                                                 if                                     (um.has(arr[i]) ==                                     true                                     ){                       
                                                 let e = um.get(arr[i]);                       
                                                 e.l = i;                       
                                                 }                       
                                   
                                                 // storing first index                       
                                                 else                                     {                       
                                                 let e =                                     new                                     index();                       
                                                 e.f = i;                       
                                                 um.set(arr[i], e);                       
                                                 }                       
                                                 }                       
                                   
                                                 let diff, max_diff = Number.MIN_VALUE;                       
           
                                                 // traversing 'um'                       
                                                 for                                     (let [key,value] of um)                       
                                                 {                       
                                                 // difference of last and first index                       
                                                 // of each element                       
                                                 diff = value.l - value.f;                       
                                   
                                                 // update 'max_dff'                       
                                                 if                                     (max_diff < diff)                       
                                                 max_diff = diff;                       
                                                 }                       
                                   
                                                 // required maximum difference                       
                                                 return                                     max_diff;                       
                         }                       
           
                         // Driver program to test above                       
                         let arr = [2, 1, 3, 4, 2, 1, 5, 1, 7];                       
                         let n = arr.length;                       
                         document.write(                                     "Maximum Difference = "                                     +maxDifference(arr, n),                                     "</br>"                                     );                       
           
                         // This code is contributed by shinjanpatra                       
           
                         </script>                       

输出：

Maximum Difference = 6

时间复杂度：O（n）本文由 阿尤什·焦哈里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章