[Java] Simple Code - Follow Up
If the range of the numbers is in [0...100], we use a bucket to collect the frequency of each number. By accumulating the frequency of elements in the bucket, w
- If the range of the numbers is in `[0...100]`, we use a bucket to collect the frequency of each number. By accumulating the frequency of elements in the bucket, we can know the median numbers.\n````\n\tclass MedianFinder {\n        int A[] = new int[101], n = 0;\n\t\t\n\t\t// O(1)\n        public void addNum(int num) {\n            A[num]++;\n            n++;\n        }\n\t\t\n\t\t// O(100) = O(1)\n        public double findMedian() {\n\t\t\n\t\t\t// find 1st median number\n            int count = 0, i = 0;\t\t\t\n            while (count < n/2) count += A[i++];\n\t\t\t\n\t\t\t// find 2nd median number\n            int j = i;\n            while (count < n/2+1) count += A[j++];\n\t\t\t\n            return (n%2 == 1) ? i : (i-1+j-1) / 2.0;\n        }\n    }\n````\n\n- If `1%` numbers are outside of the range `[0...100]`, we know that when the set of numbers is large, the median numbers must be in the range of `[0...100]`, because this range contains `99%` numbers. We don\'t need to store values of `1%` numbers, but the counts of these numbers (`countLessZero` & `countGreater100`). The `findMedian` method is almost the same, the difference is we start counting from `countLessZero` value\n````\n\tclass MedianFinder {\n        int A[] = new int[101], n = 0;\n\t\tint countLessZero = 0;\n\t\t// int countGreater100 = 0; // not needed\n\t\t\n\t\t// O(1)\n        public void addNum(int num) {\n\t\t\tif (num < 0) countLessZero++;\n\t\t\t// else if (num > 100) countGreater100++;\n\t\t\telse A[num]++;\n            n++;\n        }\n\t\t\n\t\t// O(100) = O(1)\n        public double findMedian() {\n\t\t\n\t\t\t// find 1st median number\n            int count = countLessZero, i = 0;\t\t\t\n            while (count < /2) count += A[i++];\n\t\t\t\n\t\t\t// find 2nd median number\n            int j = i;\n            while (count < n/2+1) count += A[j++];\n\t\t\t\n            return (n%2 == 1) ? i : (i-1+j-1) / 2.0;\n        }\n    }\n````\n\nInsert - `O(1)`, Find `O(1)`, Space Complexity `O(1)`\n\n
[]