โจทย์: ตารางแฮช p บัคเก็ต (0 ถึง p-1) แฮชฟังก์ชัน h(k) = k mod p บัคเก็ตใส่ได้ 1 ค่า แทรกค่าจากอาร์เรย์ X หาดัชนีที่เกิด collision แรก หากไม่มีคืน -1
Input: p=10, X=[0,21,53,41,53] → Output: 3 (ค่าที่ 4 พยายามใส่บัคเก็ต 1 แต่เต็มแล้ว)
ขั้นตอนแก้
arr := array of size p filled with 0
for i := 0 to n-1:
x := X[i]
if arr[x mod p] != 0: return i
arr[x mod p]++
return -1ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int solve(int p, vector<int> X) {
int n = X.size();
vector<int> arr(p, 0);
for (int i = 0; i < n; i++) {
int x = X[i];
if (arr[x % p]) return i;
arr[x % p]++;
}
return -1;
}
int main() {
int p = 10;
vector<int> X = {0,21,53,41,53};
cout << solve(p,X) << endl;
}Input
10, {0,21,53,41,53}Output
3
