package leetcode;

import java.util.Random;

/**
 * https://leetcode.com/problems/random-pick-with-weight/
 */
public class Problem528 {
    public static class Solution {
        private final Random random = new Random();
        private int sum;

        public Solution(int[] w) {
            for (int i : w) {
                sum += i;
            }
        }

        public int pickIndex() {
            int index = random.nextInt(sum);
            return 0;
        }
    }

    public static void main(String[] args) {
    }
}

@@ -36,16 +36,42 @@
 .Random;
+%0Aimport java.util.TreeMap;
 %0A%0A/**%0A *
@@ -191,16 +191,87 @@
 ution %7B%0A
+        private final TreeMap%3CInteger, Integer%3E map = new TreeMap%3C%3E();%0A
         
@@ -391,152 +391,216 @@
     
-for (int i : w) %7B%0A                sum += i;%0A            %7D%0A        %7D%0A%0A        public int pickIndex() %7B%0A            int index = random.nextInt(sum
+// Example:%0A            // %5B1, 3, 5%5D -%3E %5B0, 1, 1, 1, 2, 2, 2, 2, 2%5D%0A            // map -%3E %5B0 -%3E 0, 1 -%3E 1, 4 -%3E 2%5D%0A            int index = 0;%0A            for (int i : w) %7B%0A                map.put(sum, index++
 );%0A 
@@ -614,26 +614,33 @@
     
+  
-return 0;%0A
+  sum += i;%0A   
         
 %7D%0A  
@@ -635,18 +635,71 @@
         
+ 
 %7D%0A
+            System.out.println(map.toString());%0A    
     %7D%0A%0A 
@@ -705,48 +705,113 @@
     
+ 
+   
 public 
-static void main(String%5B%5D args) %7B
+int pickIndex() %7B%0A            return map.floorEntry(random.nextInt(sum)).getValue();%0A        %7D
 %0A   

Solve problem 528