ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็ม และเราต้องพิมพ์เฉพาะตัวเลขที่หารด้วยองค์ประกอบอื่นของอาร์เรย์อย่างน้อยหนึ่งรายการเท่านั้น
มาดูตัวอย่างเพื่อทำความเข้าใจแนวคิดกันดีกว่า
Input : 3 12 16 21 Output : 12 21
คำอธิบาย − 3 นั้นเล็กที่สุดจึงหารด้วยจำนวนอื่นลงตัวคือ 12 หารด้วย 3 ลงตัว, 16 หารด้วย 3 ไม่ลงตัว และ 21 ลงตัวด้วย 3 ลงตัว เราจะละเลย 3 กับ 16
วิธีง่ายๆ วิธีหนึ่งคือการตรวจสอบว่าองค์ประกอบทั้งหมดถูกหารด้วยองค์ประกอบอื่นของอาร์เรย์หรือไม่ แต่นี่ไม่ใช่วิธีแก้ปัญหาที่ดีที่สุด
การใช้แฮช อาจเป็นทางออกที่ดีกว่า เราจะเก็บองค์ประกอบของอาร์เรย์ในแฮชแล้วค้นหาองค์ประกอบสูงสุดของอาร์เรย์ จากนั้นจนถึงองค์ประกอบสูงสุดนี้ ค้นหาทวีคูณของจำนวนที่กำหนด และหากพบหลายรายการในแฮช องค์ประกอบนั้นจะถูกหารด้วยองค์ประกอบอย่างน้อยหนึ่งรายการในอาร์เรย์ เช่นนี้ เราจะพิมพ์องค์ประกอบที่หารด้วยองค์ประกอบอย่างน้อยหนึ่งรายการในอาร์เรย์
ตัวอย่าง
ตอนนี้ ตามแนวคิดนี้ เรามาสร้างโปรแกรมกันเถอะ -
#include <bits/stdc++.h>
using namespace std;
void printDivisibleNumber(int arr[], int n){
unordered_set<int> s;
int maxElement = INT_MIN;
for (int i = 0; i < n; i++) {
s.insert(arr[i]);
maxElement = max(maxElement, arr[i]);
}
unordered_set<int> res;
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
for (int j = arr[i] * 2; j <= maxElement; j += arr[i]) {
if (s.find(j) != s.end())
res.insert(j);
}
}
}
unordered_map<int, int> mp;
for (int i = 0; i <n; i++)
mp[arr[i]]++;
unordered_map<int, int>::iterator it;
vector<int> ans;
for (it = mp.begin(); it != mp.end(); it++) {
if (it->second >= 2) {
if (res.find(it->first) == res.end()) {
int val = it->second;
while (val--)
ans.push_back(it->first);
}
}
if (res.find(it->first) != res.end()) {
int val = it->second;
while (val--)
ans.push_back(it->first);
}
}
for (auto x : ans)
cout<<x<<"\t";
}
int main(){
int arr[] = {2, 4, 7 , 12 , 14 };
int n = sizeof(arr) / sizeof(arr[0]);
printDivisibleNumber(arr, n);
return 0;
} ผลลัพธ์
12 14 4
