Tuyên bố vấn đề
Cho một mảng gồm N số nguyên, hãy sắp xếp lại các phần tử của mảng sao cho phần tử mảng tiếp theo lớn hơn phần tử trước arr [i + 1]> arr [i]
Ví dụ
Nếu mảng đầu vào là {300, 400, 400, 300} thì mảng được sắp xếp lại sẽ là -
{300, 400, 300, 400}. Trong giải pháp này, chúng tôi nhận được 2 chỉ số với điều kiện arr [i + 1]> arr [i]. Do đó câu trả lời là 2.
Thuật toán
- Nếu tất cả các phần tử đều khác biệt, thì câu trả lời chỉ đơn giản là n-1 trong đó n là số phần tử trong mảng
- Nếu có các phần tử lặp lại, thì câu trả lời là n - maxFrequency
Ví dụ
Bây giờ chúng ta hãy xem một ví dụ -
#include <bits/stdc++.h>
#define MAX 1000
using namespace std;
int getMaxIndices(int *arr, int n) {
int count[MAX] = {0};
for (int i = 0; i < n; ++i) {
count[arr[i]]++;
}
int maxFrequency = 0;
for (int i = 0; i < n; ++i) {
if (count[arr[i]] > maxFrequency) {
maxFrequency = count[arr[i]];
}
}
return n - maxFrequency;
}
int main() {
int arr[] = {300, 400, 300, 400}; int n = sizeof(arr) / sizeof(arr[0]);
cout << "Answer = " << getMaxIndices(arr, n) << endl;
return 0;
} Đầu ra
Answer = 2