The implementation of the C++ algorithm to select the small number of k in an unordered array

  • 2020-05-17 06:01:07
  • OfStack

This article illustrates the implementation of the C++ algorithm for selecting the small number of k in an unordered array. I will share it with you for your reference as follows:

Select the smallest number k from an unordered integer array. k=1 is the smallest number and k=n is the largest number. Here the array can have duplicate values!

The following is a function I wrote, remember here to remember the traces I left!


// Select order in an unordered array k A small number of 
#include <iostream>
using namespace std ;
bool failed = false ;
// I'm just going to worry about the array int Type of 
int findnumber(int *array,int start , int end, int k)
{
  if(array == NULL || start > end || k < start || k > end+1 || k <= 0 )
  {
    failed = true ;
    return 0;
  }
  if(start == end)
  {
    return array[start] ;
  }
  int len = end - start + 1 ;
  int tmp = 0 ;
  int ps = rand()%len +start ;
  int tk = k ;
  while(true)
  {
   // Split two arrays 
   int f = start ;
   int t = array[ps] ;
   int equalnum = 0 ;
   for(int i = start ; i <= end ; i ++ )
   {
        if(array[i]< t )
        {
          tmp = array[f];
          array[f] = array[i];
          array[i] = tmp ;
          f ++ ;
        }else if(array[i] == t)
        {
          tmp = array[f];
          array[f] = array[i];
          array[i] = tmp ;
          f ++ ;
          equalnum ++ ;
        }
    } //end
    f--;
    if(equalnum > tk && (f - start + 1) == equalnum)
    {
      return t ;// So here's the number of records that are equal when we start with start To the end end It's all filled up with this value, so it's going to be this value, and then you're going to get stuck in a loop. 
    }
    if(tk == (f - start + 1) )
    {
      return t ;
    }
    if((f - start + 1 ) > tk )
    {
      end = f ;
    }else
    {
       start = f + 1  ;
       tk = k - start  ; // I made a mistake here, and I wrote it k=k-start , always find infinite loop when debugging. Then print k The value of theta k The value of all *** For the negative. this bug The mistake made in 1 The first run may yield the correct data, but the program crashes after multiple runs. 
     }
     len = end - start + 1 ;
     ps = rand()%len +start ;
  }
}
int main()
{
  int array[10] = {1,1,1,2,2,1,4,1,1,1};
  for(int i = 0 ; i < 10 ; i ++ )
  {
    cout<<findnumber(array,0,9,i+1)<<endl;
  }
  system("pause");
  return 0 ;
}

Think well first, analyze good problem, oneself in the brain conceived good the train of thought that writes, and think good the place that the program goes wrong to reprogram, so can be much faster, instead of 1 sees a problem to box box to type on the computer.

I hope this article is helpful to you C++ programming.


Related articles: