third minimum

general
, ,
21

Is there somebody to help me?please tell me where is my wrong

22

Here is the corrected version of your code along the necessary comments for the corrections -

Here is a better approach -

23

If u want to find kth smallest element in the array, then i will do in this manner,

procedure: find the first smallest element then mask it,then find the 2nd smallest,mask it and so on…

case1:

 if k<logn

memset(flag,1,sizeof(flag));
cin>>n>>k;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<k;i++)
{
  mini=inf;
  for(j=0;j<n;j++)
  {
    if(flag[j] && mini>a[j])
    {
      mini=a[j];
      x=j;
    }
  }
  flag[x]=0;

}

cout<<mini<<" "<<x;

Time complexity: O(k*n)

case 2: k>logn

Repeat the same procedure for finding (n-k+1)th largest element for the array

Time complexity: O((n-k+1)*n)

In all case better than nlogn sorting…

Note: U can also use my above method to do sorting in O(n^2)… :slight_smile:
Happy coding :slight_smile:

24

Why are you making base comparisons to log N ? I think n/2 is the way to go if you want to start from the other end.

25

@thezodiac1994
It would not be n/2 as complexity becomes O((n/2)*n)=O(n^2), so here sorting becomes a better option …

but yeah there is a bug… it should be:

case1: k<logn

case2: k>n-logn

case3: use sorting

thanks :wink:

26

You didnt mention sorting as a case 3 and hence I was referring to the log N term.