## Saturday, October 8, 2016

### LeetCode OJ - Random Pick Index

Problem:

Analysis:

The key idea is that we sort the array and let the number carry along with their index. When we query, we can simply binary search and pick a random index in the list.

Solution:

What piss me off is that the judge said my program ran out of memory, and there is someone else who submitted a program that is essentially the same but got accepted.

Code:

#include "stdafx.h"

// https://leetcode.com/contest/4/problems/random-pick-index/

#include "LEET_RANDOM_PICK_INDEX.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_RANDOM_PICK_INDEX
{
class Entry
{
public:
Entry(int value, size_t index) : m_value(value), m_index(index) {}
int m_value;
size_t m_index;
};

bool compareEntry(Entry i, Entry j)
{
return i.m_value < j.m_value;
}

class Solution
{
public:
Solution(vector<int> nums)
{
if (nums.size() == 0)
{
return;
}

for (size_t i = 0; i < nums.size(); i++)
{
this->m_entries.push_back(Entry(nums[i], i));
}
sort(this->m_entries.begin(), this->m_entries.end(), compareEntry);
}

int pick(int target)
{
// I have no idea how can this run out of memory :(
auto from = lower_bound(this->m_entries.begin(), this->m_entries.end(), Entry(target, 0), compareEntry);
auto to = upper_bound(this->m_entries.begin(), this->m_entries.end(), Entry(target, 0), compareEntry);
long long x = distance(from, to);
return (int)(from + rand() % x)->m_index;
}
private:
vector<Entry> m_entries;
};

};

using namespace _LEET_RANDOM_PICK_INDEX;

int LEET_RANDOM_PICK_INDEX()
{
vector<int> nums;
nums.push_back(3);
nums.push_back(2);
nums.push_back(3);
nums.push_back(1);
nums.push_back(2);
Solution solution(nums);
for (int i = 0; i < 100000000; i++)
{
cout << solution.pick(2) << endl;
}
return 0;
}