เราได้รับอาร์เรย์ขององค์ประกอบตั้งแต่ค่า 1 ถึง n องค์ประกอบบางอย่างซ้ำแล้วซ้ำอีกและบางส่วนขาดหายไป เป้าหมายคือการหาความถี่ขององค์ประกอบทั้งหมดในเวลา O(n) และช่องว่างพิเศษ O(1)
อินพุต
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) รับอาร์เรย์และขนาด n เป็นอินพุตและส่งกลับจำนวนตัวเลขระหว่าง 1 ถึง 10 ที่มีอยู่ในอาร์เรย์
-
เราสร้าง arr[i]=arr[i]-1 เพื่อให้แต่ละดัชนีเก็บความถี่ของหมายเลข i, 1 เก็บไว้ที่ดัชนี 0 เป็นต้น
-
ใช้ for loop ที่ความถี่ arr[arr[i]%10] เพิ่ม 10 เป็นค่าเดิม
-
สำหรับ x คูณ 10 จะถูกเพิ่มหากจำนวน i เกิดขึ้น x ครั้งในอาร์เรย์
-
ตอนนี้ใช้สำหรับความถี่การพิมพ์แบบวนซ้ำโดยใช้ arr[i]/10 สำหรับองค์ประกอบทั้งหมด i+1 ที่ดัชนี i
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
void printfrequency(int arr[],int n){
int i=0;
//1 becomes 0, 2 becomes 1 .....10 becomes 9 so arr[i] will have count of i
for ( i =0; i<n; i++)
arr[i] = arr[i]-1;
//as numbers are between 1-10 add 10 to all (num%10 is num itself)
for (i=0; i<n; i++)
arr[arr[i]%10] = arr[arr[i]%10] + 10;
for (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
