PriorityQueue - Java O(N*logN) | O(N)
Intuition\n Describe your first thoughts on how to solve this problem. \nUse PriorityQueue to poll the smallest K elemnent but we need to skip the element if it
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse PriorityQueue to poll the smallest K elemnent but we need to skip the element if it\'s been marked. There are two options:\n\nOption 1: wrap the number we put in to PQ as an object e.g. `List<Integer>` or `Custom object` that has index information added, so that we can mark and remove it from PQ directly when we start processing. This option is very straight forward but we have to do custom sorting in PQ, also the performance is not good due to overhead of PQ remove, custom sorting and object wrapping.\n\nOption 2: push the number index to PQ instead of value, we check on-the-fly whether the index has beem marked. If marked, we pull one extra. This logic is a bit complex and also need the custom sorting, but the performance is better.\n \n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(N*logN)$$ - from PriorityQueue\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public long[] unmarkedSumArray(int[] nums, int[][] queries) {\n        // need marked(array), lower(PriorityQueue), sum\n        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> nums[a] == nums[b] ? a - b : nums[a] - nums[b]);\n        long[] res = new long[queries.length];\n        long sum = 0;\n        for (int i = 0; i < nums.length; i++) {\n            pq.offer(i);\n            sum += nums[i];\n        }\n        for (int i = 0; i < queries.length; i++) {\n            sum -= nums[queries[i][0]];\n            nums[queries[i][0]] = 0;\n            while (!pq.isEmpty() && queries[i][1] > 0) {\n                int top = pq.poll();\n                if (nums[top] != 0) {\n                    sum -= nums[top];\n                    nums[top] = 0;\n                    queries[i][1]--;\n                }\n            }\n            res[i] = sum;\n        }\n        return res;\n    }\n}\n```
['Java']