如何在 O(1) 空间复杂度下按递减顺序打印优先队列。

huangapple go评论105阅读模式
英文:

How to Print decreasing order of the PriorityQueue in O(1) Space

问题

  1. class GFG {
  2. public static void main(String args[])throws IOException {
  3. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  4. int t = Integer.parseInt(br.readLine());
  5. while(t-- > 0) {
  6. // take array and kth element input
  7. String n_k[] = br.readLine().split(" ");
  8. // store array size in n && kth element to find in k
  9. int n = Integer.parseInt(n_k[0]);
  10. int k = Integer.parseInt(n_k[1]);
  11. // Array String input
  12. String s[] = br.readLine().split(" ");
  13. int d[] = new int[n];
  14. for(int i = 0; i < n; i++) {
  15. d[i] = Integer.parseInt(s[i]);
  16. }
  17. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
  18. // insert elements into the maxHeap
  19. for(int i = 0; i < n; i++) {
  20. maxHeap.add(d[i]);
  21. }
  22. // pop the top k elements from the maxHeap
  23. for(int i = 0; i < k; i++) {
  24. System.out.print(maxHeap.poll() + " ");
  25. }
  26. System.out.println();
  27. } // end of while
  28. } // end of main
  29. } // end of class
英文:

Am solving problems on Heaps and i want the output for a problem in decreasing order, using PriorityQueue.
<br>Input:
<br>1
<br>5 2
<br>12 5 787 1 23
<br>Output:
<br>23 787
<br> Wanted Output:
<br> 787 23

  1. class GFG {
  2. public static void main(String args[])throws IOException {
  3. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  4. int t = Integer.parseInt(br.readLine());
  5. while(t--&gt;0) {
  6. // take array and kth element iput
  7. String n_k[] = br.readLine().split(&quot; &quot;);
  8. // store array size in n &amp;&amp; kth element to find in k
  9. int n = Integer.parseInt(n_k[0]);
  10. int k = Integer.parseInt(n_k[1]);
  11. // Array String input
  12. String s[] = br.readLine().split(&quot; &quot;);
  13. int d[] = new int[n];
  14. for(int i = 0 ; i &lt; n ; i++) {
  15. d[i] = Integer.parseInt(s[i]);
  16. }
  17. PriorityQueue&lt;Integer&gt; minHeap = new PriorityQueue&lt;Integer&gt;();
  18. // delete the minimum element in the element and just keep
  19. // k greater element in the minHeap
  20. for(int i = 0 ; i &lt; n; i++) {
  21. minHeap.add(d[i]);
  22. // if size of heap increases pop tht last element
  23. if(minHeap.size()&gt;k) {
  24. minHeap.poll();
  25. }
  26. }
  27. // print remaining element
  28. //HERE IS THE PROBLEM I WANT IT IN &quot; DECREASING ORDER &quot;
  29. // it gives me Increasing order
  30. while(minHeap.size() &gt; 0) {
  31. System.out.print(minHeap.peek()+&quot; &quot;);
  32. minHeap.poll();
  33. }
  34. System.out.println();
  35. }// end of while
  36. }// end of main
  37. }// end of class

Input:
<br>1
<br>5 2
<br>12 5 787 1 23
<br>Output:
<br>23 787

答案1

得分: 1

你可以使用 Stream 来打印结果:

  1. try (Scanner scan = new Scanner(System.in)) {
  2. int totalCases = scan.nextInt();
  3. while (totalCases-- > 0) {
  4. int n = scan.nextInt();
  5. int k = scan.nextInt();
  6. Queue<Integer> minHeap = new PriorityQueue<>(k);
  7. for (int i = 0; i < n; i++) {
  8. if (minHeap.size() == k)
  9. minHeap.remove();
  10. minHeap.add(scan.nextInt());
  11. }
  12. System.out.println(minHeap.stream()
  13. .sorted(Comparator.reverseOrder())
  14. .map(String::valueOf)
  15. .collect(Collectors.joining(" ")));
  16. }
  17. }
英文:

You can use Stream to print the result:

  1. try (Scanner scan = new Scanner(System.in)) {
  2. int totalCases = scan.nextInt();
  3. while (totalCases-- &gt; 0) {
  4. int n = scan.nextInt();
  5. int k = scan.nextInt();
  6. Queue&lt;Integer&gt; minHeap = new PriorityQueue&lt;&gt;(k);
  7. for (int i = 0; i &lt; n; i++) {
  8. if (minHeap.size() == k)
  9. minHeap.remove();
  10. minHeap.add(scan.nextInt());
  11. }
  12. System.out.println(minHeap.stream()
  13. .sorted(Comparator.reverseOrder())
  14. .map(String::valueOf)
  15. .collect(Collectors.joining(&quot; &quot;)));
  16. }
  17. }

答案2

得分: 0

  1. 只需将您的代码替换为以下内容
  2. 在声明优先级队列时您可以使用反向顺序提供比较器
  3. PriorityQueue<Integer> newHeap = new PriorityQueue<>(minHeap.size(), Comparator.reverseOrder());
  4. 这里我创建了一个新的 newHeap它将以反向顺序存储所有现有元素然后执行所有现有操作
  5. 它会给出预期的答案
  6. 1
  7. 5 2
  8. 12 5 787 1 23
  9. 输出
  10. 787 23
  11. 这将对您有所帮助
  12. class GFG {
  13. public static void main(String args[]) throws IOException {
  14. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  15. int t = Integer.parseInt(br.readLine());
  16. while (t-- > 0) {
  17. String n_k[] = br.readLine().split(" ");
  18. int n = Integer.parseInt(n_k[0]);
  19. int k = Integer.parseInt(n_k[1]);
  20. String s[] = br.readLine().split(" ");
  21. int d[] = new int[n];
  22. for (int i = 0; i < n; i++) {
  23. d[i] = Integer.parseInt(s[i]);
  24. }
  25. PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  26. for (int i = 0; i < n; i++) {
  27. minHeap.add(d[i]);
  28. // if size of heap increases pop tht last element
  29. if (minHeap.size() > k) {
  30. minHeap.poll();
  31. }
  32. }
  33. PriorityQueue<Integer> newHeap = new PriorityQueue<>(minHeap.size(), Comparator.reverseOrder());
  34. newHeap.addAll(minHeap);
  35. while (newHeap.size() > 0) {
  36. System.out.print(newHeap.peek() + " ");
  37. newHeap.poll();
  38. }
  39. System.out.println();
  40. }
  41. }
  42. }
英文:

Simply replace your code with below.

While declaring priority queue , you can provide comparator with reverse order.

PriorityQueue<Integer> newHeap = new PriorityQueue(minHeap.size(),Comparator.reverseOrder());

Here i had created one newHeap which will store all existing elements in reverseOrder and then doing all existing operation as it is.

It's giving expected answer.

  1. 1
  2. 5 2
  3. 12 5 787 1 23
  4. O/P
  5. 787 23

This will help you.

  1. class GFG {
  2. public static void main(String args[]) throws IOException {
  3. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  4. int t = Integer.parseInt(br.readLine());
  5. while (t-- &gt; 0) {
  6. String n_k[] = br.readLine().split(&quot; &quot;);
  7. int n = Integer.parseInt(n_k[0]);
  8. int k = Integer.parseInt(n_k[1]);
  9. String s[] = br.readLine().split(&quot; &quot;);
  10. int d[] = new int[n];
  11. for (int i = 0; i &lt; n; i++) {
  12. d[i] = Integer.parseInt(s[i]);
  13. }
  14. PriorityQueue&lt;Integer&gt; minHeap = new PriorityQueue&lt;Integer&gt;();
  15. for (int i = 0; i &lt; n; i++) {
  16. minHeap.add(d[i]);
  17. // if size of heap increases pop tht last element
  18. if (minHeap.size() &gt; k) {
  19. minHeap.poll();
  20. }
  21. }
  22. PriorityQueue&lt;Integer&gt; newHeap = new PriorityQueue(minHeap.size(), Comparator.reverseOrder());
  23. newHeap.addAll(minHeap);
  24. while (newHeap.size() &gt; 0) {
  25. System.out.print(newHeap.peek() + &quot; &quot;);
  26. newHeap.poll();
  27. }
  28. System.out.println();
  29. }
  30. }
  31. }

huangapple
  • 本文由 发表于 2020年8月17日 04:20:19
  • 转载请务必保留本文链接:https://go.coder-hub.com/63441593.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定