Minimum swaps and K together Java solution
//together elements less than or equal to k
//idea is to use sliding window concept
// here we have window with size = elements less than or equal to k
//look for greater elements in that window size
//move window one by one and check which element was removed or added
//find minimum elements > k in that window as they are elements needs to swap
public static int minSwap(int arr[],int n,int k)
{
int c=0,gk=0; // gk = greather than k,c= less than k
for(int i=0;i<n;++i)
{
if(arr[i]<=k)
++c;
}
for(int i=0;i<c;++i)
{
if(arr[i]>k)
++gk;
}
int res=gk;
// System.out.println(gk+" "+c);
for(int i=0,j=c;j<n;++i,++j)
{
if(arr[i]>k)
--gk;
if(arr[j]>k)
++gk;
res=Math.min(gk,res);
}
return res;
}
//idea is to use sliding window concept
// here we have window with size = elements less than or equal to k
//look for greater elements in that window size
//move window one by one and check which element was removed or added
//find minimum elements > k in that window as they are elements needs to swap
public static int minSwap(int arr[],int n,int k)
{
int c=0,gk=0; // gk = greather than k,c= less than k
for(int i=0;i<n;++i)
{
if(arr[i]<=k)
++c;
}
for(int i=0;i<c;++i)
{
if(arr[i]>k)
++gk;
}
int res=gk;
// System.out.println(gk+" "+c);
for(int i=0,j=c;j<n;++i,++j)
{
if(arr[i]>k)
--gk;
if(arr[j]>k)
++gk;
res=Math.min(gk,res);
}
return res;
}
0 Comments:
Post a Comment