Задачи с собеседований по максимальным числам: как решить?

Существует такая задача:
нужно написать функцию, которая принимает на вход массив чисел (неотсортированных, допустим целых), возвращает также массив в котором содержатся:
- максимальное число А1
- три других максимальных числа А2, А3, А4, которые при перемножении дают А1

Начал писать функцию с выделением max и сортировкой, потом начал писать вложенные циклы, но понял, что будет слишком много условий и проверок.
Есть мысль, что тут могут помочь регулярки, но пока не знаю, как это реализовать.
  • Вопрос задан
  • 1631 просмотр
Решения вопроса 2
Отсортировать по убыванию и двумя циклами – некошерно?
на JS
const maxprod = arr => {
  const a = arr.slice().sort((a, b) => b - a);
  const max = a[0];
  const len = a.length;
  let iter = 0;
    
  for (let i = 1; i < len - 2; i++) {
    iter++;
    const A2 = a[i];
    const x2 = max / A2;
    if (!Number.isInteger(x2)) continue;
      
    for (let j = i + 1; j < len - 1; j++) {
      iter++;
      const A3 = a[j];
      const x3 = x2 / A3;
      if (!Number.isInteger(x3)) continue;
      
      if (!!~a.indexOf(x3)) {
        return [max, A2, A3, x3, iter]);
      }
    }
  }
  
  return false;
}

По сути циклов три, т.к. indexOf() всё равно перебирает массив.

Из оптимизаций только отсечение мелких хвостов, когда произведение становится меньше искомого.
И проверка каждого кандидата на делимость.
В хвост результата пихается ещё число итераций.

Тесты
[
  [20,5,3,2,2], // [ 20, 5, 2, 2, 3 ]
  [7,9,4,60,5,3,2,2], // [ 60, 5, 4, 3, 4 ]
  [1,2,3,199], // false
  [2430,2431,2431,2431,1,1,1,2,3,5,7,9,11,13,15,17,19,23], // [ 2431, 17, 13, 11, 8 ]
].forEach(test => console.log(test, maxprod(test)));
Ответ написан
yellow79
@yellow79
Senior Software Engineer
Накидал решение "влоб". Работает 100% правильно, если я правильно понял суть задачи. Требует дополнительной памяти https://play.golang.com/p/ics2FIIFw7b
Ответ написан
Пригласить эксперта
Ответы на вопрос 6
angrySCV
@angrySCV
machine learning, programming, startuping
регулярки тебе никак не помогут в этой задаче
вот тут почитай про этот тип задач
Ответ написан
BojackHorseman
@BojackHorseman
...в творческом отпуске...
не знаешь как решать - решай перебором. в худшем случае получишь решение высокой вычислительной сложности, но рабочее и за адекватное время. потом предложи автору вопроса обосновать наличие решения с полиномиальной сложностью для этой задачи.
Ответ написан
mindtester
@mindtester
делаю странные вещи..чаще на C#..иногда за деньги
Adamos,
2. Раскладываете А1 на множители (это куда быстрее перебора всего массива на комбинации из трех элементов).
все зависит от размеров чисел. для больших чисел это может быть сверсхложной задачей

Nik_Set_7, пока не заметил уточнения - гарантированно ли присутствие делителей в общем списке?
в общем случае, максимальное находится за один полный проход. это необходимо, но и достаточно.

а пляски с делителями зависят от нюансов - размер списка? он помещается оперативной памяти? или доступен только последовательно, из медленного источника?.. если делители гарантировано присутствуют, их можно найти за.. думаю количество проходов однозначно будет меньше чем для любого алгоритма сортировки )) upd если список существенно длинне 3х элементов ))

и существует ли гарантия присутствия делителей в списке? если нет +значения не велики +список большой +источник последовательный и медленный, возможно, Adamos будет прав. ну а для значений не более 8 битного целого, скорее будет прав однозначно ))
Ответ написан
dimonchik2013
@dimonchik2013
почему ракеты не летают как птицы?
допустим целых

хороший прикид

там, случаем, что множители целые "допустим" не отвалилось?
Ответ написан
@John_Nash
coder
числа целые, положительные

Тогда, если считать, что сумма должна быть максимальной. То все просто.
Отсортировать. Взять 1е максимальное. A1
Взять 2е максимальное (цикл от максимума до минимума) A2
Разделить на второе максимальное (текущее). Получить цикл 2го уровня. В нем также брать значения меньше или равн. результата деления
Разделить частное на A3, проверить наличие результата в списке значений.

Как только найдено, можно завершать
Ответ написан
@vvs46
Если я правильно понял задачу, моё решение в лоб:
Source
#include <iostream>
#include <windows.h>
#include <vector>
std::vector<int> DoTheJob(std::vector<int> v)
{

    int tmp;
    std::vector<int> result;
    bool flagfound = false;


    //sorting
    for(int i=0;i<v.size()-1;i++)
    {
        for (int j=i+1;j<v.size();j++)
        {
            if(v[j]>v[i])
            {
                tmp=v[i];
                v[i]=v[j];
                v[j]=tmp;
            };
        };
    };

    //sorting_end
    result.push_back(v[0]);
    for(int i=1; i<v.size()-2;i++)
    {
        if (flagfound)
                {
                    break;
                }
        for(int j=i+1;j<v.size()-1;j++)

        {
            if (flagfound)
                {
                    break;
                };
            for(int k=j+1;k<v.size();k++)
            {
                if (flagfound)
                {
                    break;
                };
                if(v[0]==v[i]*v[j]*v[k])
                    {
                        result.push_back(v[i]);
                        result.push_back(v[j]);
                        result.push_back(v[k]);
                        flagfound = true;
                    }
            };
        };
    }
    return result;
};
int main()
{   int q = 10;
    std::vector<int> v;
    for (int i=0;i<q;i++)
    {
        v.push_back((GetTickCount()+rand())%10);
        std::cout<< v[i]<<" ";
    };
    std::cout<<std::endl;
    std::vector<int> solution = DoTheJob(v);
    std::cout << "Max element: "<<solution[0];
    if (solution.size()==4)
    {
        std::cout<<", multipliers: "<<solution[1]<<", "<< solution[2]<<", "<<solution[3];
    }
    else
    std::cout<< ", no multipliers.";
    return 0;
}
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
CSort Барнаул
от 40 000 до 90 000 руб.
SegmentStream Москва
от 250 000 до 350 000 руб.
от 120 000 руб.
16 июл. 2019, в 23:23
5000 руб./за проект
16 июл. 2019, в 22:43
10000 руб./за проект