首页 > 代码库 > 求数组中出现次数第二多的数字——哈希表
求数组中出现次数第二多的数字——哈希表
hash表实现
完整代码:
#include <iostream> using namespace std; enum STATUS{ EMPTY, EXIT }; int _hash(int num, int n, int* hashtable, int* status) { int index = num % n; if (status[index] == EMPTY){//当前位置没有映射任何数 status[index] = EXIT; } else if (status[index] == EXIT&&hashtable[index] == num){//当前位置已经映射了数字且恰好和将要被映射的数相等 ; } else{//当前位置已经映射了数字但不是将要被映射的数,需要二次探测找这个将要被映射的数的正确下标 int i = 1; while ((status[index] == EXIT) && (hashtable[index] != num)){ index += (2 * i + 1);//哈希的二次探测 } status[index] = EXIT; } return index; } int solution(int* arr, int n) { if (arr == NULL || n <= 0)return 0; int* hashtable = new int[n]; int* status = new int[n]; int* count = new int[n]; memset(hashtable, 0, n*sizeof(int)); for (int i = 0; i < n; ++i) status[i] = EMPTY; memset(count, 0, n*sizeof(int)); for (int i = 0; i < n; ++i){ int index = _hash(arr[i], n, hashtable,status); hashtable[index] = arr[i]; ++count[index]; } /*for (int i = 0; i<n; ++i){ cout << hashtable[i] << " "; } cout << endl; for (int i = 0; i<n; ++i){ cout << count[i] << " "; } cout << endl;*/ //找出出现次数第二多的数字在hashtable中的下标 int max1 = count[0], max2 = count[1];//输入数据应合法,否则会崩溃 int min; for (int i = 2; i < n; ++i){ int f = max1, s = max2, t = count[i]; max1 = f>s ? f : s; min = f>s ? s : f; max2 = min > t ? min : t; } int index = max1 > max2 ? max2 : max1; int i = 0; int max = -1; while (count[i] != index){++i;} max = hashtable[i]; delete[] hashtable; delete[] status; delete[] count; return 0; } int main() { int arr[] = { 0, 14, 5, 8, 0, 14, 35, 36, 87, 0, 10, 10, 10, 10, 10, 5, 5, 6 }; cout<<solution(arr, sizeof(arr)/sizeof(arr[0]))<<endl; system("pause"); }
本文出自 “零蛋蛋” 博客,谢绝转载!
求数组中出现次数第二多的数字——哈希表
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。