0528 solved.

liuyubobobo · liuyubobobo · commit 8dba54bab0ca · 2018-08-28T16:35:32.000-07:00
diff --git a/0528-Random-Pick-with-Weight/cpp-0528/CMakeLists.txt b/0528-Random-Pick-with-Weight/cpp-0528/CMakeLists.txt
@@ -0,0 +1,7 @@
+cmake_minimum_required(VERSION 3.5)
+project(cpp_0528)
+
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
+
+set(SOURCE_FILES main.cpp)
+add_executable(cpp_0528 ${SOURCE_FILES})
diff --git a/0528-Random-Pick-with-Weight/cpp-0528/main.cpp b/0528-Random-Pick-with-Weight/cpp-0528/main.cpp
@@ -0,0 +1,43 @@
+/// Source : https://leetcode.com/problems/random-pick-with-weight/description/
+/// Author : liuyubobobo
+/// Time   : 2018-08-28
+
+#include <iostream>
+#include <vector>
+#include <algorithm>
+
+using namespace std;
+
+
+/// Pre-Sum and Binary Search
+/// Time Complexity: init: O(n)
+///                  pickIndex: O(logn)
+/// Space Complexity: O(n)
+class Solution {
+
+private:
+    vector<int> sum;
+
+public:
+    Solution(vector<int> w) {
+        sum.clear();
+        sum.push_back(0);
+        for(int e: w)
+            sum.push_back(sum.back() + e);
+    }
+
+    int pickIndex() {
+
+        int randNum = rand() % sum.back();
+        int index = lower_bound(sum.begin(), sum.end(), randNum) - sum.begin();
+        if(sum[index] != randNum)
+            index --;
+        return index;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -316,6 +316,8 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 518 | [Coin Change 2](https://leetcode.com/problems/coin-change-2/description/) | [无] | [C++](0518-Coin-Change-2/cpp-0518/) | | |
 | 519 | [Random Flip Matrix](https://leetcode.com/problems/random-flip-matrix/description/) | [solution](https://leetcode.com/problems/random-flip-matrix/solution/) | [C++](0519-Random-Flip-Matrix/cpp-0519/) | | |
 | | | | | | |
+| 528 | [Random Pick with Weight](https://leetcode.com/problems/random-pick-with-weight/description/) | [solution](https://leetcode.com/problems/random-pick-with-weight/solution/) | [C++](0528-Random-Pick-with-Weight/cpp-0528/) | | |
+| | | | | | |
 | 530 | [Minimum Absolute Difference in BST](https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/) | [无] | | [Java](0530-Minimum-Absolute-Difference-in-BST/java-0530/src/) | |
 | | | | | | |
 | 541 | [Reverse String II](https://leetcode.com/problems/reverse-string-ii/description/) | [solution](https://leetcode.com/problems/reverse-string-ii/solution/) | [C++](0541-Reverse-String-II/cpp-0541/) | | |
