LintCode/IndexMatch.java at master · shawnfan/LintCode · GitHub



LintCode/IndexMatch.java at master · shawnfan/LintCode · GitHub

有序, 假设有这样的数字:target. target 左边的数字，一定不比index大，target右边的数字，一定比index大。 这样可以binary search.O(logn) ``` /* 来自网上uber面经：给一个有序数组（不含重复），返回任意一个数字，这个数字的值和它的数组下标相等 可能的follow up: 1. 如果含有重复数字怎么办？ 如果有序，也没问题，还是binary search 2. 另一种follow up:找这样数字的边界. 如果存在，那么和index match的一定在一块. 找到任何一个candiate, 找边界，也可以binary search,只是match的condition不同罢了。

Read full article from LintCode/IndexMatch.java at master · shawnfan/LintCode · GitHub


No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts