C++, нахождение 3 максимальных значений в массиве, где разница между этими значениями является одним из параметров

Question

Я должен найти 3 значения max в массиве реальных данных. Проблема заключается в том, что эти 3 значения должны варьироваться в зависимости от конкретного минимального значения (которое является параметром). Это означает, что если у меня есть массив с 10 элементами {1,2,3,4,5,6,7,8,9,10}, то 3 max значения в этом массиве равны 8,9,10, но если значение параметр, например, «2», эти 3 значения max должны меняться как минимум около «2», поэтому реальные максимальные значения в моем случае будут 10, 8, 6. Я считаю, что алгоритм программы будет выглядеть следующим образом: :

1) найти 3 максимальные значения (петля) 2) проверить, если они изменяются по меньшей мере примерно от параметра 2а), если да, вернуть эти 3 значения 2b), если нет, то вернитесь к петле, поиск снова 3 но игнорирует это значение, которое не удовлетворяет условию?

Я не могу представить реальный код в C++ для этого решения. Может ли кто-нибудь дать совет, как это сделать?

Answer 1

Один из подходов может быть таким: 1) Сортировка массива 2) Выберите последний k, здесь, в соответствии с вашим вопросом 3. Как выбрать с параметром, как с минимальной разницей d, здесь 2;

1. Идите из последнего массива и проверьте, больше ли разность двух элементов, чем d, затем выберите последний элемент.
2. продолжайте повторять, пока не найдете k элементов.

Answer 2

Проще говоря, вы можете использовать oporator%, например, если ваш параметр равен 2 и имеет имя par, как в вашем примере, вы можете использовать следующий оператор внутри цикла. % выделяет число, чтобы посмотреть, не отличается ли оно от 0.23 типов результатов.

Использование следующего оператора: если (число% пар == 0)

поможет определить, если число делится этим пар без каких-либо после того, как цифры 0.xx.

При этом вы также можете использовать функцию и удалять/копировать из массива, у вас есть максимальное значение. Для этого вам придется заранее использовать цикл, чтобы определить, какая из них самая большая.

А что касается возврата, вы можете сделать целочисленный массив и отправить его как возврат.

Answer 3

Если массив отсортирован, вы можете просто сравнить значения с самым высоким значением в порядке убывания. Если значение не меньше наивысшего значения минус параметр, то проверьте самое высокое значение.

Так что псевдо-код будет выглядеть примерно так

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 
} 

Вы можете изменить его, чтобы построить массив и вернуть его, а затем проверить, если массив имеет размер 3.

Answer 4

легче, чем сортировка просто сканируйте массив 3 раза. В первый раз, найдите макс. В следующий раз, найти наибольшее число < = (макс - р) и т.д.

Вы изучали Big-O обозначение для оценки эффективности алгоритма?

Сравните время сортировки & поиска (п * Л.Г. (2) п + п) к тому времени, искать 3 раза (3 * п) безубыточности производительности происходит при довольно малом значении п.