คำชี้แจงปัญหา
ด้วยอาร์เรย์ของจำนวนเต็ม N ให้จัดเรียงองค์ประกอบอาร์เรย์ใหม่เพื่อให้องค์ประกอบอาร์เรย์ถัดไปมีค่ามากกว่าองค์ประกอบก่อนหน้า arr[i+1]> arr[i]
ตัวอย่าง
หากอาร์เรย์อินพุตเป็น {300, 400, 400, 300} อาร์เรย์ที่จัดเรียงใหม่จะเป็น −
{300, 400, 300, 400} ในวิธีแก้ปัญหานี้ เราได้ 2 ดัชนีที่มีเงื่อนไข arr[i+1]> arr[i] ดังนั้นคำตอบคือ 2.
อัลกอริทึม
- หากองค์ประกอบทั้งหมดแตกต่างกัน คำตอบก็คือ n-1 โดยที่ n คือจำนวนองค์ประกอบในอาร์เรย์
- หากมีองค์ประกอบที่เกิดซ้ำ คำตอบคือ n – maxFrequency
ตัวอย่าง
เรามาดูตัวอย่างกัน −
#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;
} ผลลัพธ์
Answer = 2
