package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

 Note:
 The array size can be very large. Solution that uses too much extra space will not pass the judge.

 Example:

 int[] nums = new int[] {1,2,3,3,3};
 Solution solution = new Solution(nums);

 // pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
 solution.pick(3);

 // pick(1) should return 0. Since in the array only nums[0] is equal to 1.
 solution.pick(1);*/
public class _398 {

//TODO: use reservoir sampling to solve it again

    class Solution {
        //brute force
        int[] input;
        java.util.Random rand = new java.util.Random();

        public Solution(int[] nums) {
            input = nums;
        }

        public int pick(int target) {
            List<Integer> list = new ArrayList();
            for (int i = 0; i < input.length; i++) {
                if (input[i] == target) {
                    list.add(i);
                }
            }
            if (list.size() == 1) {
                return list.get(0);
            }
            int randomIndex = rand.nextInt(list.size());
            return list.get(randomIndex);
        }
    }


    class SolutionMemoryLimitExceeded {

        private Map<Integer, List<Integer>> map = new HashMap();
        java.util.Random rand = new java.util.Random();

        public SolutionMemoryLimitExceeded(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                if (map.containsKey(nums[i])) {
                    List<Integer> list = map.get(nums[i]);
                    list.add(i);
                    map.put(nums[i], list);
                } else {
                    List<Integer> list = new ArrayList();
                    list.add(i);
                    map.put(nums[i], list);
                }
            }
        }

        public int pick(int target) {
            List<Integer> list = map.get(target);
            if (list.size() == 1) {
                return list.get(0);
            }
            int randomIndex = rand.nextInt(list.size());
            return list.get(randomIndex);
        }
    }
}

@@ -78,66 +78,51 @@
 til.
-HashMap;%0Aimport java.util.List;%0Aimport java.util.Map;%0A%0A/**
+List;%0A%0A/**%0A * 398. Random Pick Index%0A *%0A * 
 Give
@@ -169,16 +169,19 @@
 licates,
+%0A *
  randoml
@@ -746,16 +746,20 @@
 _398 %7B%0A%0A
+    
 //TODO: 
@@ -800,24 +800,38 @@
  again%0A%0A    
+public static 
 class Soluti
@@ -1463,956 +1463,6 @@
   %7D%0A
-%0A%0A    class SolutionMemoryLimitExceeded %7B%0A%0A        private Map%3CInteger, List%3CInteger%3E%3E map = new HashMap();%0A        java.util.Random rand = new java.util.Random();%0A%0A        public SolutionMemoryLimitExceeded(int%5B%5D nums) %7B%0A            for (int i = 0; i %3C nums.length; i++) %7B%0A                if (map.containsKey(nums%5Bi%5D)) %7B%0A                    List%3CInteger%3E list = map.get(nums%5Bi%5D);%0A                    list.add(i);%0A                    map.put(nums%5Bi%5D, list);%0A                %7D else %7B%0A                    List%3CInteger%3E list = new ArrayList();%0A                    list.add(i);%0A                    map.put(nums%5Bi%5D, list);%0A                %7D%0A            %7D%0A        %7D%0A%0A        public int pick(int target) %7B%0A            List%3CInteger%3E list = map.get(target);%0A            if (list.size() == 1) %7B%0A                return list.get(0);%0A            %7D%0A            int randomIndex = rand.nextInt(list.size());%0A            return list.get(randomIndex);%0A        %7D%0A    %7D%0A
 %7D%0A

refactor 398