Khoảng cách tối đa giữa hai lần xuất hiện của cùng một phần tử trong mảng trong C

Chúng ta được cung cấp với một mảng các số nguyên. Mảng có nhiều lần xuất hiện của các phần tử giống nhau. Nhiệm vụ ở đây là tìm khoảng cách lớn nhất giữa hai phần tử giống nhau bất kỳ của mảng. Chúng tôi sẽ chọn từng phần tử từ mảng bắt đầu từ bên trái. Sau đó, chúng tôi sẽ tìm lần xuất hiện cuối cùng của cùng một số đó và lưu trữ sự khác biệt giữa các chỉ mục. Bây giờ nếu mức chênh lệch này là tối đa thì hãy trả lại.

Đầu vào

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

Đầu ra −Khoảng cách tối đa giữa hai lần xuất hiện của cùng một phần tử trong mảng - 4

Giải thích - Các số lặp lại có chỉ mục -

1. 1, first index 0, last index 3 distance=3-0-1=2
2. 2, first index 1, last index 6 distance=6-1-1=4
3. 5, first index 7, last index 9 distance=9-7-1=1
Maximum distance between two occurrences of same element : 4

Đầu vào

Arr[] = { 10,20,1,10,10,21,12,0 }

Đầu ra −Khoảng cách tối đa giữa hai lần xuất hiện của cùng một phần tử trong mảng - 3

Giải thích - Các số lặp lại có chỉ mục -

1. 10 first index 0, last index 4 distance=4-0-1=3
Maximum distance between two occurrences of same element : 3

Lưu ý - nếu mảng đầu vào không có số lặp lại, thì trả về -1

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Chúng tôi lấy một mảng số nguyên có các số lặp lại là Arr []

• Hàm maxDistance (int arr [], int n) được sử dụng để tính toán Khoảng cách tối đa giữa hai lần xuất hiện của cùng một phần tử.

• Chúng tôi khởi tạo biến maxD bằng -1.

• Bên trong vòng lặp for duyệt qua mảng các số nguyên ngay từ đầu.

• Trong vòng lặp for lồng nhau đi qua các phần tử còn lại và tìm kiếm các phần lặp lại nếu có. (if (arr [i] ==arr [j]).

• Nếu nó là đúng thì tính toán sự khác biệt giữa các số bằng cách trừ các chỉ số. (temp =j-i-1)

• Nếu giá trị này là lớn nhất được tìm thấy cho đến nay, thì hãy lưu trữ nó trong maxD

• Trả về maxD sau khi duyệt qua toàn bộ mảng.

Ví dụ

#include <stdio.h>
#include <math.h>
int maxDistance(int arr[],int n){
   int size = n;
   int maxD = -1;
   for (int i = 0; i < n - 1; i++)
      for (int j = i + 1; j < n; j++)
         if (arr[i] == arr[j]){
            int temp=abs(j-i-1);
            maxD = maxD>temp?maxD:temp;
         }
   return maxD;
}
// Driver code
int main(){
   int Arr[] = {1,2,4,1,3,4,2,5,6,5};
   printf("Maximum distance between two occurrences of same element in array:%d", maxDistance(Arr,10) );
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Maximum distance between two occurrences of same element in array − 4