Chúng ta được cung cấp với một mảng các số nguyên có kích thước N. Mảng bao gồm các số nguyên theo thứ tự ngẫu nhiên. Nhiệm vụ là tìm ra sự khác biệt lớn nhất giữa chỉ số đầu tiên và chỉ số cuối cùng của một phần tử trong mảng. Chúng ta phải tìm một số xuất hiện hai lần trong mảng và sự khác biệt giữa các chỉ mục của nó là lớn nhất. Nếu có nhiều cặp như vậy hơn thì chúng tôi sẽ lưu trữ mức chênh lệch tối đa giữa các chỉ mục.
Đầu vào
Arr[] = { 2,1,3,1,3,2,5,5 }. Đầu ra −Chênh lệch tối đa giữa chỉ mục đầu tiên và chỉ số cuối cùng của một phần tử trong mảng - 5
Giải thích - Các cặp phần tử và sự khác biệt giữa các chỉ mục của chúng như sau -
(2,2) Arr[0] and Arr[5] 5-0=5 max difference till now is 5 (1,1) Arr[1] and Arr[3] 3-1=2 max difference till now is 5 (3,3) Arr[2] and Arr[4] 4-2=2 max difference till now is 5 (5,5) Arr[6] and Arr[7] 7-6=1 max difference till now is 5
Đầu vào
Arr[] = { 2,2,3,4,8,3,4,4,8,7 }. Đầu ra −Sự khác biệt tối đa giữa chỉ số đầu tiên và chỉ số cuối cùng của một phần tử trong mảng - 4
Giải thích - Các cặp phần tử và sự khác biệt giữa các chỉ mục của chúng như sau -
(2,2) Arr[0] and Arr[1] ; 1-0=1; max difference till now is 1 (3,3) Arr[2] and Arr[5] ; 5-2=3; max difference till now is 3 (4,4,4) Arr[3],Arr[6],Arr[7] ; 7-6=1,6-3=3,7-3=4; max difference till now is 4 (8,8) Arr[4] and Arr[8] ; 8-4=4 ; max difference till now is 4
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Khai báo một mảng số nguyên chứa các số lặp lại theo thứ tự ngẫu nhiên. (Arr [])
-
Tạo một biến để lưu trữ kích thước của mảng. (N)
-
Hàm maxDifference (int Arr [], int n) được sử dụng để tính toán sự khác biệt lớn nhất (maxD) giữa chỉ mục đầu tiên và chỉ mục cuối cùng của một phần tử trong một mảng.
-
Bên trong maxDifference (), chúng tôi đã khai báo maxD được sử dụng để lưu trữ sự khác biệt về chỉ mục tối đa được tìm thấy cho đến nay.
-
Bắt đầu từ phần tử đầu tiên (chỉ số i =0) duyệt qua mảng bằng vòng lặp for.
-
Trong vòng lặp for lồng nhau đi qua mảng còn lại (j =i + 1) cho đến khi đạt đến chỉ mục cuối cùng.
-
Nếu chúng tôi tìm thấy phần tử giống như Arr [i], chúng tôi tính toán sự khác biệt giữa các chỉ số i, j của nó và nếu nó lớn hơn giá trị trước đó của maxD, chúng tôi cập nhật maxD.
-
Tiếp tục điều này cho đến khi kết thúc cả hai vòng lặp.
-
Trả về kết quả được lưu trữ trong maxD.
Ví dụ
#include <stdio.h>
int maxDifference(int arr[],int n){
int maxD=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(arr[i]==arr[j] && (j-i)>maxD)
maxD=j-i;
}
}
return maxD;
}
int main(){
int Arr[] = {1, 4, 1, 3, 3, 5, 4, 5, 2};
int N = sizeof(Arr) / sizeof(Arr[0]);
printf("Maximum difference between first and last indexes of an element in array : %d" ,maxDifference(Arr, N);
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 difference between first and last indexes of an element in array : 5