最大値最小値を求める方法時間複雑度O(n)

1833 ワード

#include<iostream>    

#include <iostream>

#include <bitset>

#include <ctime>

using namespace std;



template <size_t UpperBound> class Urand{      // 

  bitset<UpperBound> used;

public:

	Urand(){ srand(time(0)); }

	double operator() ();

};



template<size_t UpperBound>

inline double Urand<UpperBound>::operator()()

{

	if(used.count() == UpperBound)

		used.reset();

	size_t newval;

	while(used[newval = rand() % UpperBound])

		;

	used[newval] = true;

	return newval*0.1;

}



int main(int argc, char* argv[])

{

	Urand<10> u;

	double darr[10];

	double first = 0.0;

	double second = 0.0;

	double min = 0.0;

	double max = 0.0;

	for ( int i = 0; i < 10; ++i)

	{

		darr[i] = u();

	}

    

	int num = sizeof(darr)/sizeof(darr[0]);

	bool flag = false;



	if( num%2==0 )

    {

        flag = true;

    }

	else

	{

        flag = false;

	}

    

	if(flag)

	{  

	   int i= 0;

	   first = darr[0];

	   second = darr[1];

	   if(first<second)

	   {

          min = first;

		  max = second;

	   }

	   else

	   {

          min = second;

		  max = first;

	   }

	}

	else

	{

		min = darr[0];

		max = darr[0];

	}

	

	   for( flag? i=2 : i=1; i<num; i+=2 )

	   {

            if( darr[i]<darr[i+1] )

			{

			    if( min>darr[i] ) 

				{

                    min = darr[i];

				}

				if( max<darr[i+1] )

				{

                    max = darr[i+1];

				}

			}

			else

			{

                if( min>darr[i+1] )

				{

                    min = darr[i+1];

				}

				if( max<darr[i])

				{

					max = darr[i];

				}



			}

	   }

	

    cout<<"Max :"<<max<<endl;

	cout<<"Min :"<<min<<endl;

	return 0;

}