Decimal dominants


https://www.cnblogs.com/evasean/p/7273857.html
Decimal dominants. Given an array with n keys, design an algorithm to find all values that occur more than  n/10 times. The expected running time of your algorithm should be linear.
分析:
直观上将n个元素遍历一遍,并记录每个元素出现的次数就可以实现,虽然时间复杂度是O(n),但是空间复杂度却高达n,这肯定不是该题目的初衷。对于n个元素来说,出现n/10次的元素最多有10个,那么出现超过n/10次的元素最多不超过9个,所以需要9个额外空间auxs就能满足需求。
这9个辅助空间aux怎么使用呢?可采用俄罗斯方块的消去一行的思路。只不过这里消去一行的情况是该行中元素各不相同。
1. 遍历数组array中的每个元素array[i]
2. 如果array[i]在aux中存在,将其在aux中的计数+1
3. 如果array[i]在aux中不存在
  3.1 如果aux未满,将其放入aux中,并记录其个数为1
  3.2 如果aux已满,将aux中已经存在的各个元素的计数都减去1,直到某个元素的个数变成0,将array[i]放入aux中该位置处,并记录其个数为1
4. 出现次数超过n/10的元素在array遍历完了之后,还会继续存在于aux中,当然aux中可存在着位于array后方但出现次数不满足要求的元素。这时只需要遍历aux的同时再遍历一遍array,记录aux中各个元素在array中出现的次数,将其中出现次数真正超过n/10的元素找出来即可。
Naively, we could just count the number of occurrences of each elements.
  • define a hash map from the values to the number of occurrence of those values in the array.
  • iterate through the array and populate the hash map.
  • iterate through the hash map and get keys with values greater than or equal to n/10.
This takes ~N time and ~N space.
Solution 2
We can optimize the first solution to reduce the memory usage. The key point leading to this optimization is that if the array is of size n, there can be at most 9 elements that occur more than n/10 times. If we suppose that the array had 10 elements that occur more than n/10 times, then we will have more than n elements in the array, which is a contradiction.
With this realization in mind, we can solve the problem using 9 buckets with Boyer-Moore majority vote algorithm.
Basically, we can remember 9 elements along with the number of times they have been seen so far in a loop. When a remembered element is seen, its count is incremented. If an element which is not remembered is seen, we fit it into a slot if one is free. If no slot is free, subtract 1 from all counts. If the count is 0, forget the element.
This takes ~N time and ~1 space.
Solution 3
We can also use a selection algorithm to solve the problem in a linear time. If we imagine the array was sorted in a descending order, we can narrow our candidates to 9 elements, namely (n/10)-th, (2n/10)-th, … (9n/10)-th elements.
In this imaginary sorted version of the array, any elements left to (n/10)-th array cannot occur more than n/10 times because there won’t be enough room.
Using QuickSelect, we can get (n/10)-th largest element from the array without sorting the entire array. After checking if (n/10)-th largest element is decimal dominant, we apply the same procedure to the array including and to the right side of (n/10)-th largest element. This means we check for (2n/10)-th largest element, and so on.
This takes ~N time (9 calls to QuickSelect) and ~1 space.

https://raw.githubusercontent.com/phareskrad/algs4/master/jobinterviewquestions/QuickSort.java
        public DecimalDominants(int[] a, int k) {
            A = a;
            N = a.length;
            K = k;

            buildCounts(a);
        }

        private void buildCounts(int[] a) {
            for (int i = 0; i < N; i++) {
                if (counts.containsKey(i)) counts.put(i, counts.get(i) + 1);
                else counts.put(i, 1);
                if (counts.keySet().size() >= K) removeCounts();
            }
        }

        private void removeCounts() {
            for (int k : counts.keySet()) {
                int c = counts.get(k);
                if (c > 1) counts.put(k, c - 1);
                else counts.remove(k);
            }
        }

        public Iterable<Integer> find() { //brute force
            Bag<Integer> result = new Bag<Integer>();
            for (int k : counts.keySet()) {
                if (count(k) > N/K) result.add(k);
            }
            return result;
        }

        private int count(int k) {
            int count = 0;
            for (int i = 0; i < N; i++) {
                if (A[i] == k) count++;
            }
            return count;
        }
    }



 7 public class ElemsMoreThanNDivTenTimes {
 8     
 9     private class Element{//辅助空间元素定义,用来记录元素值及其出现次数
10         public int element;
11         public int count;
12         public Element(int e,int c){
13             this.element = e;
14             this.count = c;
15         }
16     };
17     private Element[] elems = new Element[9]; //申请9个辅助空间
18     
19     
20     public ArrayList<Integer> findElements(int[] arrays){
21         int n = arrays.length;
22         for(int k=0;k<9;k++){
23             elems[k] = new Element(0,0); //辅助空间初始化
24         }
25         for(int i=0;i<n;i++){
26             int index = findIndex(arrays[i]);
27             if(index >= 0)
28                 elems[index].count ++;
29             else
30                 addToElems(arrays[i]);
31         }
32         return verifyElems(arrays);
33     }
34     
35     private int findIndex(int e){
36         for(int k = 0; k<9;k++){
37             if(elems[k].element == e)
38                 return k;
39             else if(elems[k].count == 0){
40                 elems[k].element = e;
41                 return k;
42             }
43         }
44         return -1;
45     }
46     private void addToElems(int e){
47         boolean insertFlag = false;
48         while(!insertFlag){
49             for(int k=0; k<9;k++){
50                 elems[k].count --;
51                 if(elems[k].count <= 0){
52                     elems[k].element = e;
53                     elems[k].count = 1;
54                     insertFlag = true;
55                     break;
56                 }
57             }
58         }
59     }
60     private ArrayList<Integer> verifyElems(int[] arrays){
61         int n = arrays.length;
62         for(int k = 0; k< 9; k++){
63             elems[k].count = 0;
64             for(int i = 0; i< n;i++){
65                 if(arrays[i]==elems[k].element)
66                     elems[k].count++;
67             }
68         }
69         ArrayList<Integer> elemList = new ArrayList<Integer>();
70         for(int k = 0; k< 9; k++){
71             if(elems[k].count > n/10)
72                 elemList.add(elems[k].element);
73         }
74         return elemList;
75     }



Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts