เราได้รับอาเรย์สมาชิกมีค่า 1 ถึง n บางตัวซ้ำ บางตัวหาย เป้าหมายคือหาความถี่ของทุกสมาชิกใน O(n) time และ O(1) extra space
อินพุต
Arr[] = {1, 2, 2, 3, 4, 4, 4, 5}
เอาต์พุต
1→1, 2→2, 3→1, 4→3, 5→5
คำอธิบาย − สมาชิกสูงสุดคือ 5 แสดงจำนวนครั้งที่แต่ละตัวปรากฏ
อินพุต
Arr[] = {1, 4, 4, 5, 5, 5, 5}
เอาต์พุต
1→1, 2→0, 3→0, 4→2, 5→4
คำอธิบาย − สมาชิกสูงสุดคือ 5
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- โปรแกรมทำงานสำหรับอาเรย์ที่มีตัวเลข 1 ถึง 10
- ฟังก์ชัน printfrequency(int arr[], int n) พิมพ์ความถี่ 1 ถึง 10
- ทำ arr[i] = arr[i] - 1 ทำให้ index 0 เก็บความถี่ของ 1, index 1 เก็บ 2, ...
- ลูป i=0..n-1: arr[arr[i]%10] += 10 (เพิ่ม 10 ทุกครั้งที่เจอตัวเลขนั้น)
- ลูป i=0..9: พิมพ์ i+1 และ arr[i]/10 (ความถี่)
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
void printfrequency(int arr[], int n) {
for (int i = 0; i < n; i++)
arr[i] = arr[i] - 1;
for (int i = 0; i < n; i++)
arr[arr[i] % 10] = arr[arr[i] % 10] + 10;
for (int i = 0; i < 10; i++)
cout << i + 1 << " -> " << arr[i] / 10 << endl;
}
int main() {
int arr[] = {2, 3, 3, 2, 5, 6, 7, 7, 7, 8, 8, 9, 9};
int n = sizeof(arr) / sizeof(arr[0]);
printfrequency(arr, n);
return 0;
}
ผลลัพธ์
1 -> 0 2 -> 2 3 -> 2 4 -> 0 5 -> 1 6 -> 1 7 -> 3 8 -> 2 9 -> 5 10 -> 0
