ความแตกต่างสูงสุดระหว่างดัชนีแรกและดัชนีสุดท้ายขององค์ประกอบในอาร์เรย์


ระดับความยาก กลาง
ถามบ่อยใน แอคโคไลท์ อเมซอน ธุดงค์ MakeMyTrip Ola Cabs SAP Labs
แถว กัญชา

สมมติว่าคุณมีไฟล์ แถว 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. ส่งกลับผลต่างสูงสุด

คำอธิบาย

เราได้รับไฟล์ จำนวนเต็ม อาร์เรย์เราต้องหาความแตกต่างระหว่างดัชนีแรกและดัชนีสุดท้ายของแต่ละค่าของอาร์เรย์ ค้นหาความแตกต่างสูงสุดสำหรับตัวเลขใด ๆ ระหว่างดัชนีแรกและดัชนีสุดท้าย สำหรับสิ่งนี้เราจะใช้ hashing. เราจะใช้องค์ประกอบอาร์เรย์และจะค้นหาดัชนีแรกและดัชนีสุดท้ายหรือเมื่อเกิดขึ้นครั้งแรกและครั้งสุดท้าย

สำรวจแผนที่หลังจากใส่องค์ประกอบทั้งหมดและดัชนีแรกและดัชนีสุดท้ายลงในแผนที่ ตอนนี้เลือกแต่ละองค์ประกอบจากนั้นใช้ดัชนีแรกและดัชนีสุดท้ายและจะพบความแตกต่างที่ควรเป็นค่าสูงสุดทั้งหมด เราสามารถใช้ตัวแปร ความแตกต่างสูงสุด เพื่อจับตาดูความแตกต่างสูงสุด เราจะใช้คลาสและอ็อบเจ็กต์เพื่อจัดเก็บดัชนีแรกและดัชนีสุดท้ายของทุกองค์ประกอบ

ให้เราพิจารณาตัวอย่าง:

ตัวอย่าง

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

เรามีอินพุตอาร์เรย์ ในการแก้ปัญหานี้เราจะใช้คลาส เราจะมองหาทุกองค์ประกอบหากมีการสำรวจเป็นครั้งแรก จากนั้นเราจะจัดเก็บดัชนีเป็นดัชนีแรกและเมื่อองค์ประกอบเดียวกันนั้นกลับมาอีกครั้ง จากนั้นทุกครั้งเราจะจัดเก็บดัชนีเป็นดัชนีที่สอง ด้วยวิธีนี้เรามีแผนที่ดังนี้:

แผนที่: 1-> 3: null,

2-> 0: 6,

3-> 1, null,

4-> 4: null,

5-> 2: 7,

6-> 5: null

เราจะสำรวจแผนที่และเราจะนำแต่ละค่าและตรวจสอบความแตกต่างของดัชนี เราจะละเลยค่าทั้งหมดที่มีค่าว่าง เราจึงมี 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 ' คือจำนวนองค์ประกอบในอาร์เรย์