แนวคิด
ได้รับอาร์เรย์สองอาร์เรย์ของจำนวนเต็ม M ตัว สมมติอาร์เรย์ C โดยสมาชิกที่ i จะเป็น d*a[i] + b[i] โดย d เป็นจำนวนจริง bất kỳ ให้พิมพ์ d 使得อาร์เรย์ C มีศูนย์มากที่สุด และพิมพ์จำนวนศูนย์ด้วย
อินพุต
a[] = {15, 40, 45} b[] = {4, 5, 6}
เอาต์พุต
Value of d is: -0.133333 The number of zeros in array C is: 1 If we choose d as -0.133333 then we get one zero in the array C which is the maximum possible.
วิธีการ
ทำตามขั้นตอนด้านล่างเพื่อแก้ปัญหา:
- เขียนสมการใหม่เป็น d = -b[i]/a[i]
- ใช้แฮชเทเบิลนับจำนวนครั้งที่เกิดขึ้นมากที่สุดของจำนวนจริงเพื่อหาค่า d
- สรุปว่าจำนวนศูนย์จะเป็น largest count + (จำนวนคู่ a[i] และ b[i] ที่ทั้งคู่เป็น 0)
ตัวอย่างโค้ด C++
// โปรแกรม C++ นำไปใช้วิธีการข้างต้น
#include <bits/stdc++.h>
using namespace std;
// ฟังก์ชันหาค่า d และจำนวนศูนย์ในอาร์เรย์
void findDandZeros1(int a[], int b[], int m) {
// แฮชเทเบิล
unordered_map<long double, int> mpp1;
int count1 = 0;
// วนลูปสมาชิกที่ i
for (int i = 0; i < m; i++) {
// หากทั้งคู่ไม่เป็น 0
if (b[i] != 0 && a[i] != 0) {
long double val1 = (long double)(-1.0 * b[i]) / (long double)(a[i]);
mpp1[val1] += 1;
}
// หากทั้งคู่เป็น 0
else if (b[i] == 0 && a[i] == 0)
count1 += 1;
}
// หา d ที่เกิดขึ้นมากที่สุด
int maxi1 = 0;
for (auto it : mpp1) {
maxi1 = max(it.second, maxi1);
}
// พิมพ์ d ที่เกิดขึ้นมากที่สุด
for (auto it : mpp1) {
if (it.second == maxi1) {
cout << "Value of d is: " << it.first << endl;
break;
}
}
// พิมพ์จำนวนศูนย์
cout << "The number of zeros in array C is: " << maxi1 + count1;
}
// โค้ดหลัก
int main() {
int a[] = {15, 40, 45};
int b[] = {4, 5, 6};
int m = sizeof(a) / sizeof(a[0]);
findDandZeros1(a, b, m);
return 0;
}
เอาต์พุต
Value of d is: -0.133333 The number of zeros in array C is: 1
