CODEWITHSUNDEEP
c++arraysloopsmax
K.Kacper
K.Kacper

Reputation: 45

C++, finding 3 max values in array, where difference between these values is one of the parameter

I have to find 3 max values in array of real data. The problem is the fact that these 3 values must vary about particular, minimum value (which is the parameter). It means that if I have an array with 10 elements {1,2,3,4,5,6,7,8,9,10} 3 max values in this array are 8,9,10 but if the value of the parameter is for example "2" these 3 max values must vary at least about "2", so the real max values in my case would be 10, 8, 6. I believe that the algorithm of the program would look like this:

1) find 3 max values (loop) 2) verify if they vary at least about the parameter 2a) if yes return these 3 values 2b) if not, go back to the loop, search again 3 values but ignore this value which doesn't fulfill the condition?

I can't imagine the real code in c++ for this solution. Can anybody give a piece of advice how to do it?

Upvotes: 3

Views: 155

Answers (4)

joeking
joeking

Reputation: 2106

Easier than sorting is simply scan the array 3 times. The first time, find the max. The next time, find the largest number <= (max - p) etc.

Have you studied Big-O notation for evaluation of algorithm performance?

Compare the time to sort & search (n * lg(2)n + n) to the time to search 3 times (3*n) Break-even performance happens at a pretty small value of n.

Upvotes: 2

Trevor
Trevor

Reputation: 366

If the array is sorted, you could just compare the values to the highest value in descending order. If the value is not less than the highest value minus the parameter, then check the highest value.

So the pseudo code would look something like

Bool getHighestThree(int minDifference)
{
   Int returnArray[3]
   Int valuesFound = 0
   myArray.sort()
   For (int I = myArray.size - 2; i >= 0; --i)
   {
      If (myArray[myArray.size() - 1] - minDifference > myArray[i])
      {
         returnArray[valuesFound++]
      }
      If (valuesFound == 3)
      {
         Return true
      }
   }
   Return false
}

You could change it to build the array and return it, and then check if the array is of size 3.

Upvotes: 0

TotalyNotUbisoft
TotalyNotUbisoft

Reputation: 63

It's quite simple to be frank, you can use the oporator % for example if your parameter is 2 and named par like in your example, you can use the next statement inside a loop. the % devides a number to look if it devides with no 0.23 types of results.

Using the next statement: if(number % par == 0)

Will help you determine if the number is devided by that par without any after the 0.xx numbers.

While doing so you could also use a function and remove/copy from the array you have the max value. To do that you will have to use a loop run beforehand to determine which is the biggest.

And as for the return you can make an integer array and send it as a return.

Upvotes: 0

vk3105
vk3105

Reputation: 94

One approach can be like this: 1) Sort the array 2) Pick last k, here as per your question 3.How to pick with a parameter like with minimum difference of d, here 2;

  1. Iterate from last of the array and check if the difference of the two elements is greater that d then pick the last element.
  2. keep on iterating till you find k elements.

Upvotes: 0

Related Questions