演算法›Ch2 分治法
第 4 題/共 12 題
◀ AL 4/12
4. Divide-and-Conquer、Hashing、多數元素
#AL-02-004難Divide-and-ConquerHashing多數元素

Consider a hash function hh that maps numerous keys into an array AA, indexed from 0 to n−1n-1. The concern is that excessive collisions arising from the hashed keys can potentially cause inefficiency within the hash table. The following pseudocode, while not complete, implements a function that utilizes the divide-and-conquer strategy to identify the case where strictly more than half of the keys share the same hash value. The function takes the hash function hh and the subarray AA with the index range from lowlow to highhigh as input and returns the majority hash value shared by over ⌊(high−low+1)/2⌋\lfloor (high-low+1)/2 \rfloor keys. If the keys stored in the subarray A[low..high]A[low..high] do not have such a majority hash value, the function returns −1-1.

1: function FindMajorityHashValue(hh, AA, lowlow, highhigh) 2: if low=highlow = high then return h(A[low])h(A[low]) end if 3: mid←⌊(low+high)/2⌋mid \leftarrow \lfloor (low+high)/2 \rfloor 4: leftMajority←leftMajority \leftarrow FindMajorityHashValue(hh, AA, lowlow, midmid) 5: rightMajority←rightMajority \leftarrow FindMajorityHashValue(hh, AA, mid+1mid+1, highhigh) 6: leftCount←leftCount \leftarrow CountElement(AA, lowlow, highhigh, leftMajorityleftMajority) 7: rightCount←rightCount \leftarrow CountElement(AA, lowlow, highhigh, rightMajorityrightMajority) 8: [待填空] 9: end function

In the pseudocode, CountElement(AA, lowlow, highhigh, valval) calculates and returns the count of keys in the subarray A[low..high]A[low..high] whose hashed values are equal to the given valval. Please select the correct description(s) below.

📄 台大113
跳轉到第題
▤完整推導請見《WH 資工筆記 · 演算法》Ch2 分治法
本章題號 · 1–12 / 12