สมมติว่าเรามีตัวเลข p และอาร์เรย์ X อื่นที่มีองค์ประกอบ n ตัว มีตารางแฮชพร้อมถัง p ที่เก็บข้อมูลมีหมายเลขตั้งแต่ 0 ถึง p-1 เราต้องการแทรกตัวเลข n จาก X สมมติว่าสำหรับ X[i] ถังจะถูกเลือกโดยฟังก์ชันแฮช h(X[i]) โดยที่ h(k) =k mod p ที่เก็บข้อมูลหนึ่งรายการไม่สามารถมีองค์ประกอบได้มากกว่าหนึ่งรายการ หากเราต้องการแทรกตัวเลขลงในถังที่เต็มไปแล้ว เราบอกว่า "การชนกัน" เกิดขึ้น เราต้องส่งคืนดัชนีที่มีการชนกัน หากไม่มีการชน ให้กลับ -1
ดังนั้นหากอินพุตเป็นเหมือน p =10; X =[0, 21, 53, 41, 53] จากนั้นผลลัพธ์จะเป็น 3 เพราะอันแรกจะถูกแทรกเข้าไปใน 0, อันที่สองที่ 1, อันที่สามที่ 3 แต่อันที่ 4 จะพยายามแทรกลงใน 1 แต่ มีการชนกัน ดัชนีอยู่ที่ 3 ที่นี่
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
n := size of X Define an array arr of size: p and fill with 0 for initialize i := 0, when i < n, update (increase i by 1), do: x := X[i] if arr[x mod p] is non-zero, then: return i increase arr[x mod p] by 1 return -1
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
int solve(int p, vector<int> X){
int n = X.size();
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;
} อินพุต
10, { 0, 21, 53, 41, 53 } ผลลัพธ์
3
