アルゴリズム問題を解く 10 - ハッシュで検索

問題

Given an array A of integers, find an integer k that is not present in A.
Assume that the integers are 32-bit signed integers.
( Algorithms for Interviews より引用 )

ヒント

ハッシュの写像．

解答

#include <iostream>
#include <vector>
using namespace std;

static const int MAX = 100;

void InitList(vector<int>& v) {

 v.push_back(32);
 v.push_back(55);
 v.push_back(11);
 v.push_back(42);
 v.push_back(98);
 v.push_back(51);
 v.push_back(80);
 v.push_back(6);

}

void BucketSort(vector<int>& dest, const vector<int>& src) {

 dest.resize(MAX);
 for( int i = 0;i < MAX;i++ )
  dest[i] = false;
 for( vector<int>::const_iterator iter = src.begin();iter != src.end();iter++ ) {
  dest[*iter] = true;
 }
}

bool found(const vector<int> A, int k) {

 vector<int>::const_iterator iter;
 return A[k];
 
}

int main() {

 vector<int> v;
 vector<int> sorted;
 InitList(v);
 BucketSort(sorted,v);
 cout << found(sorted,42) << endl;
 cout << found(sorted,44) << endl;

 return 0;
}