โจทย์
ได้รับอาร์เรย์ N จำนวนเต็ม จัดเรียงใหม่องค์ประกอบอาร์เรย์ เพื่อให้องค์ประกอบถัดไปมากกว่าองค์ประกอบก่อนหน้า arr[i+1] > arr[i]
ตัวอย่าง
ถ้าอินพุตอาร์เรย์คือ {300, 400, 400, 300} อาร์เรย์ที่จัดเรียงใหม่จะเป็น
{300, 400, 300, 400} ในคำตอบนี้ เราได้ 2 Index ที่ตรงเงื่อนไข 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
