힙(우선순위 큐)
배열에서 k번째로 큰 요소 찾기
TC:O(NlogN) 힙 정렬은 힙을 구축하는 데 nlogn 시간이 걸립니다.
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int i : nums){
q.add(i);
while(!q.isEmpty() && q.size() > k){
q.remove();
}
}
return q.peek();
}
}
K 최대 합계 조합
TC: O(N^2), for using two for loops
import java.util.*;
public class Solution{
public static ArrayList<Integer> kMaxSumCombination(ArrayList<Integer> a, ArrayList<Integer> b, int n, int k){
// Write your code here.
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int i : a)
for(int j : b)
if(q.size()<k)
q.add(i+j);
else
if(q.peek() < i+j){
q.remove();
q.add(i+j);
}
ArrayList<Integer> list = new ArrayList<>();
while(!q.isEmpty()) list.add(0,q.remove()); // it will add values at index 0 only by that way values will keep on shifting
return list;
}
}
n개의 정렬된 배열 병합
TC: O(N^2) + O(2*N^2log(N))
import java.util.*;
public class Solution
{
public static ArrayList<Integer> mergeKSortedArrays(ArrayList<ArrayList<Integer>> kArrays, int k)
{
PriorityQueue<Integer> q = new PriorityQueue<>();
for(ArrayList<Integer> l : kArrays){
for(Integer i : l){
q.add(i);
}
}
ArrayList<Integer> list = new ArrayList<>();
while(!q.isEmpty()){
list.add(q.remove());
}
return list;
}
}
배열 요소의 최대 xor
TC: O(N*MLogM), where N is size of queries list, M is size of arr List and LogM is the cost of adding value to priority queue
import java.util.*;
public class Solution {
public static ArrayList<Integer> maxXorQueries(ArrayList<Integer> arr, ArrayList<ArrayList<Integer>> queries) {
PriorityQueue<Integer> q = new PriorityQueue<>((a,b)-> b-a);
ArrayList<Integer> result = new ArrayList<>();
for( int i =0;i<queries.size();i++){
int X = queries.get(i).get(0);
int A = queries.get(i).get(1);
for(Integer j : arr){
if(j<=A){
q.add(X^j);
}
}
if(!q.isEmpty()){
result.add(q.remove());
}
else result.add(-1);
q.clear();
}
return result;
}
}
이것은 TLE로 이어질 것입니다
따라서 최적화된 솔루션은 O(N*M)에서 이를 달성할 수 있습니다(우선 순위 큐를 사용하지 않음).
import java.util.*;
public class Solution {
public static ArrayList<Integer> maxXorQueries(ArrayList<Integer> arr, ArrayList<ArrayList<Integer>> queries) {
ArrayList<Integer> result = new ArrayList<>();
for( int i =0;i<queries.size();i++){
int X = queries.get(i).get(0);
int A = queries.get(i).get(1);
int max = -1;
for(Integer j : arr){
if(j<=A){
max = Integer.max(max,X^j);
}
}
result.add(max);
}
return result;
}
}
Reference
이 문제에 관하여(힙(우선순위 큐)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://dev.to/prashantrmishra/heappriority-queue-4c4f
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int i : nums){
q.add(i);
while(!q.isEmpty() && q.size() > k){
q.remove();
}
}
return q.peek();
}
}
TC: O(N^2), for using two for loops
import java.util.*;
public class Solution{
public static ArrayList<Integer> kMaxSumCombination(ArrayList<Integer> a, ArrayList<Integer> b, int n, int k){
// Write your code here.
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int i : a)
for(int j : b)
if(q.size()<k)
q.add(i+j);
else
if(q.peek() < i+j){
q.remove();
q.add(i+j);
}
ArrayList<Integer> list = new ArrayList<>();
while(!q.isEmpty()) list.add(0,q.remove()); // it will add values at index 0 only by that way values will keep on shifting
return list;
}
}
n개의 정렬된 배열 병합
TC: O(N^2) + O(2*N^2log(N))
import java.util.*;
public class Solution
{
public static ArrayList<Integer> mergeKSortedArrays(ArrayList<ArrayList<Integer>> kArrays, int k)
{
PriorityQueue<Integer> q = new PriorityQueue<>();
for(ArrayList<Integer> l : kArrays){
for(Integer i : l){
q.add(i);
}
}
ArrayList<Integer> list = new ArrayList<>();
while(!q.isEmpty()){
list.add(q.remove());
}
return list;
}
}
배열 요소의 최대 xor
TC: O(N*MLogM), where N is size of queries list, M is size of arr List and LogM is the cost of adding value to priority queue
import java.util.*;
public class Solution {
public static ArrayList<Integer> maxXorQueries(ArrayList<Integer> arr, ArrayList<ArrayList<Integer>> queries) {
PriorityQueue<Integer> q = new PriorityQueue<>((a,b)-> b-a);
ArrayList<Integer> result = new ArrayList<>();
for( int i =0;i<queries.size();i++){
int X = queries.get(i).get(0);
int A = queries.get(i).get(1);
for(Integer j : arr){
if(j<=A){
q.add(X^j);
}
}
if(!q.isEmpty()){
result.add(q.remove());
}
else result.add(-1);
q.clear();
}
return result;
}
}
이것은 TLE로 이어질 것입니다
따라서 최적화된 솔루션은 O(N*M)에서 이를 달성할 수 있습니다(우선 순위 큐를 사용하지 않음).
import java.util.*;
public class Solution {
public static ArrayList<Integer> maxXorQueries(ArrayList<Integer> arr, ArrayList<ArrayList<Integer>> queries) {
ArrayList<Integer> result = new ArrayList<>();
for( int i =0;i<queries.size();i++){
int X = queries.get(i).get(0);
int A = queries.get(i).get(1);
int max = -1;
for(Integer j : arr){
if(j<=A){
max = Integer.max(max,X^j);
}
}
result.add(max);
}
return result;
}
}
Reference
이 문제에 관하여(힙(우선순위 큐)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://dev.to/prashantrmishra/heappriority-queue-4c4f
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import java.util.*;
public class Solution
{
public static ArrayList<Integer> mergeKSortedArrays(ArrayList<ArrayList<Integer>> kArrays, int k)
{
PriorityQueue<Integer> q = new PriorityQueue<>();
for(ArrayList<Integer> l : kArrays){
for(Integer i : l){
q.add(i);
}
}
ArrayList<Integer> list = new ArrayList<>();
while(!q.isEmpty()){
list.add(q.remove());
}
return list;
}
}
TC: O(N*MLogM), where N is size of queries list, M is size of arr List and LogM is the cost of adding value to priority queue
import java.util.*;
public class Solution {
public static ArrayList<Integer> maxXorQueries(ArrayList<Integer> arr, ArrayList<ArrayList<Integer>> queries) {
PriorityQueue<Integer> q = new PriorityQueue<>((a,b)-> b-a);
ArrayList<Integer> result = new ArrayList<>();
for( int i =0;i<queries.size();i++){
int X = queries.get(i).get(0);
int A = queries.get(i).get(1);
for(Integer j : arr){
if(j<=A){
q.add(X^j);
}
}
if(!q.isEmpty()){
result.add(q.remove());
}
else result.add(-1);
q.clear();
}
return result;
}
}
이것은 TLE로 이어질 것입니다
따라서 최적화된 솔루션은 O(N*M)에서 이를 달성할 수 있습니다(우선 순위 큐를 사용하지 않음).
import java.util.*;
public class Solution {
public static ArrayList<Integer> maxXorQueries(ArrayList<Integer> arr, ArrayList<ArrayList<Integer>> queries) {
ArrayList<Integer> result = new ArrayList<>();
for( int i =0;i<queries.size();i++){
int X = queries.get(i).get(0);
int A = queries.get(i).get(1);
int max = -1;
for(Integer j : arr){
if(j<=A){
max = Integer.max(max,X^j);
}
}
result.add(max);
}
return result;
}
}
Reference
이 문제에 관하여(힙(우선순위 큐)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/prashantrmishra/heappriority-queue-4c4f텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)