Java Clean Solution | Weekly Contest
Code\n\n// class Solution {\n//     private int greatestCount(List<Integer> list, int num){\n//         int count =0;\n//         for(int i=0; i<list.size(); i+
# Code\n```\n// class Solution {\n//     private int greatestCount(List<Integer> list, int num){\n//         int count =0;\n//         for(int i=0; i<list.size(); i++){\n//             if(list.get(i) > num) count++;\n//         }    \n//         return count;\n//     }\n    \n    \n//     public int[] resultArray(int[] nums) {\n//         List<Integer> list1 = new ArrayList<>();\n//         List<Integer> list2 = new ArrayList<>();\n//         list1.add(nums[0]);\n//         list2.add(nums[1]);\n        \n//         for(int i=2; i<nums.length; i++){\n//             int l1 = greatestCount(list1, nums[i]);\n//             int l2 = greatestCount(list2, nums[i]);\n//             if(l1 == l2){\n//                 if(list1.size()>list2.size()){\n//                     list2.add(nums[i]);\n//                 } else{\n//                     list1.add(nums[i]);\n//                 }\n//             } else if ( l1 < l2){\n//                 list2.add(nums[i]);\n//             } else{\n//                 list1.add(nums[i]);\n//             }\n//         }\n        \n//         int idx =0;\n//         for(int i=0; i<list1.size(); i++){\n//             nums[idx++] = list1.get(i);\n//         }\n//         for(int i=0; i<list2.size(); i++){\n//             nums[idx++] = list2.get(i);\n//         }\n//         return nums;\n        \n//     }\n// }\n\n\nclass Solution {\n    int n;\n    FenwickTree BIT1, BIT2;\n    \n    public int[] resultArray(int[] nums) {\n        n = nums.length; HashSet<Integer> set = new HashSet<Integer>();\n        for (int i = 0; i < n; i++){\n            set.add(nums[i]);\n        }\n        ArrayList<Integer> arr = new ArrayList<Integer>(set); Collections.sort(arr);\n        HashMap<Integer, Integer> compressMap = new HashMap<Integer, Integer>(), reverseMap = new HashMap<Integer, Integer>();\n        for (int i = 0; i < arr.size(); i++){\n            compressMap.put(arr.get(i), i+1);\n            reverseMap.put(i+1, arr.get(i));\n        }\n        for (int i = 0; i < n; i++){\n            nums[i] = compressMap.get(nums[i]);\n        }\n        ArrayList<Integer> a = new ArrayList<Integer>(), b = new ArrayList<Integer>(); BIT1 = new FenwickTree(n); BIT2 = new FenwickTree(n);\n        a.add(nums[0]); b.add(nums[1]); BIT1.update(nums[0], 1); BIT2.update(nums[1], 1); \n        for (int i = 2; i < n; i++){\n            int c1 = BIT1.sumRange(nums[i]+1, n), c2 = BIT2.sumRange(nums[i]+1, n);\n            if (c1 > c2) {\n                a.add(nums[i]); BIT1.update(nums[i], 1);\n            }\n            else if (c1 < c2){\n                b.add(nums[i]); BIT2.update(nums[i], 1);\n            }\n            else { // c1 == c2\n                if (a.size() <= b.size()){\n                    a.add(nums[i]); BIT1.update(nums[i], 1);\n                }\n                else {\n                    b.add(nums[i]); BIT2.update(nums[i], 1);\n                }\n            }\n        }\n        int[] ret = new int[n];\n        for (int i = 0; i < a.size(); i++) ret[i] = reverseMap.get(a.get(i));\n        for (int i = a.size(); i < n; i++) ret[i] = reverseMap.get(b.get(i-a.size()));\n        return ret;\n    }\n    \n    class FenwickTree {\n        int n;\n        int[] BIT;\n\n        FenwickTree(int n){\n            this.n = n;\n            BIT = new int[n+1];\n        }\n\n        void update(int idx, int v) {\n            for (int i = idx; i <= n; i += i&-i) {\n                BIT[i] += v;\n            }\n        }\n\n        int query(int idx) {\n            int ret = 0;\n            for (int i = idx; i > 0; i -= i&-i) {\n                ret += BIT[i];\n            }\n            return ret;\n        }\n\n        int sumRange(int l, int r) {\n            if (r < l) {\n                return 0;\n            }\n            if (l != 0) {\n                return query(r) - query(l-1);\n            }\n            return query(r);\n        }\n    }\n}\n```
['Array', 'Tree', 'Sorting', 'Java']