Оптимизировать код

@plzvtl · Регистрация: 27.10.2018

Author24 — интернет-сервис помощи студентам

Для решения задачи :
"Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

Example

For a = [2, 1, 3, 5, 3, 2], the output should be firstDuplicate(a) = 3.

There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than the second occurrence of 2 does, so the answer is 3.

For a = [2, 2], the output should be firstDuplicate(a) = 2;

For a = [2, 4, 3, 5, 1], the output should be firstDuplicate(a) = -1.

Input/Output

[execution time limit] 0.5 seconds (cpp)

[input] array.integer a

Guaranteed constraints:
1 ≤ a.length ≤ 105,
1 ≤ a[i] ≤ a.length.

[output] integer

The element in a that occurs in the array more than once and has the minimal index for its second occurrence. If there are no such elements, return -1."
Я написал такой код :

C++

int firstDuplicate(std::vector<int> a) 
{
int temp2 = -1,j3=a.size() ,j2=j3 ;
for(int i = 0; i < j3;++i)
{
for(int j = i+1; j < j3;++j)
{
if(a[i] == a[j] && j < j2)
{
j2 = j;
temp2=a[i];
break;
}
}
}
return temp2;
}

Но данный код не проходит тест за максимальное допустимое время (0.5 секунды).
Пожалуйста помогите оптимизировать данный код или придумать другой алгоритм.

@plzvtl · 15.07.2019, 03:47 **[ТС]**

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

@Yetty · 15.07.2019, 03:54

plzvtl, мне показалось, что Вы хотите разобраться, почему именно Ваш вариант не проходит тесты, а код
nalbe666 с другим алгоритмом, и пытался сбросить наиболее близкий к Вашему алгоритму вариант.

@plzvtl · 15.07.2019, 04:01 **[ТС]**

Сообщение от Yetty

разобраться

Да , это имеет смысл.
По поводу начинать с i , так в моем примере я начинаю с i+1.

Добавлено через 2 минуты
после этого так то и "i !=j" стало лишним потому что мы с +1 начинаем

@Yetty · 15.07.2019, 04:03

Сообщение от plzvtl

в моем примере я начинаю с i+1

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

@plzvtl · 15.07.2019, 04:08 **[ТС]**

Yetty, результат тот же, могу кинуть скрин , но я не понимаю зачем начинать с i а не i+1 если сразу проверка в if не проходит при j=i

@Yetty · 15.07.2019, 04:15

Сообщение от plzvtl

могу кинуть скрин

зачем скрин, если результат тот же ? там 2 теста вроде не проходит, проверьте ещё с Вашей поправкой:

C++

int firstDuplicate(vector<int> &a) 
{    
    int n=a.size(), value=-1;
    
    for (int i = 0; i < n; i++)           
        for (int j = i+1; j < n; j++)
        if (a[i]==a[j]) {n=j;value=a[i];break;}
    return value;
}

@plzvtl · 15.07.2019, 04:17 **[ТС]**

Сообщение от Yetty

проверьте

Проверил , все еще нет.

@plzvtl 57 / 43 / 12 Регистрация: 27.10.2018 Сообщений: 454
	15.07.2019, 03:47 [ТС]	21
	Yetty, мне не трудно пробовать , но я все таки спрошу : зачем? Помогли уже ж. 0

@Yetty 7437 / 5029 / 2892 Регистрация: 18.12.2017 Сообщений: 15,692
	15.07.2019, 03:54	22
	plzvtl, мне показалось, что Вы хотите разобраться, почему именно Ваш вариант не проходит тесты, а код nalbe666 с другим алгоритмом, и пытался сбросить наиболее близкий к Вашему алгоритму вариант. 0

@plzvtl 57 / 43 / 12 Регистрация: 27.10.2018 Сообщений: 454
	15.07.2019, 04:01 [ТС]	23
	Сообщение от Yetty разобраться Да , это имеет смысл. По поводу начинать с i , так в моем примере я начинаю с i+1. Добавлено через 2 минуты после этого так то и "i !=j" стало лишним потому что мы с +1 начинаем 0

@plzvtl 57 / 43 / 12 Регистрация: 27.10.2018 Сообщений: 454
	15.07.2019, 04:08 [ТС]	25
	Yetty, результат тот же, могу кинуть скрин , но я не понимаю зачем начинать с i а не i+1 если сразу проверка в if не проходит при j=i 0

Новые блоги и статьи
Счётчик на базе сумматоров + регистров и генератора сигналов согласования. Hrethgir 07.01.2025 Создан с целью проверки скорости асинхронной логики: ранее описанного сумматора и предополагаемых fast регистров. Регистры созданы на базе ранее описанного, предполагаемого fast триггера. То-есть. . .	Как перейти с Options API на Composition API в Vue.js BasicMan 06.01.2025 Почему переход на Composition API актуален В мире современной веб-разработки фреймворк Vue. js продолжает эволюционировать, предлагая разработчикам все более совершенные инструменты для создания. . .	Архитектура современных процессоров inter-admin 06.01.2025 Процессор (центральный процессор, ЦП) является основным вычислительным устройством компьютера, которое выполняет обработку данных и управляет работой всех остальных компонентов системы. Архитектура. . .	История создания реляционной модели баз данных, правила Кодда Programming 06.01.2025 Предпосылки создания реляционной модели В конце 1960-х годов компьютерная индустрия столкнулась с серьезными проблемами в области управления данными. Существовавшие на тот момент модели данных -. . .	Полезные поделки на Arduino, которые можно сделать самому raxper 06.01.2025 Arduino как платформа для творчества Arduino представляет собой удивительную платформу для технического творчества, которая открывает безграничные возможности для создания уникальных проектов. Эта. . .	Подборка решений задач на Python IT_Exp 06.01.2025 Целью данной подборки является предоставление возможности ознакомиться с различными задачами и их решениями на Python, что может быть полезно как для начинающих, так и для опытных программистов. . . .
С чего начать программировать микроконтроллеры raxper 06.01.2025 Введение в мир микроконтроллеров Микроконтроллеры стали неотъемлемой частью современного мира, окружая нас повсюду: от простых бытовых приборов до сложных промышленных систем. Эти маленькие. . .	Из чего собрать игровой компьютер inter-admin 06.01.2025 Сборка игрового компьютера требует особого внимания к выбору комплектующих и их совместимости. Правильно собранный игровой ПК не только обеспечивает комфортный геймплей в современных играх, но и. . .	Обновление сайта www.historian.by Reglage 05.01.2025 Обещал подвести итоги 2024 года для сайта. Однако начну с того, что изменилось за неделю. Добавил краткий урок по последовательности действий при анализе вредоносных файлов и значительно улучшил урок. . .	Как использовать GraphQL в C# с HotChocolate Programming 05.01.2025 GraphQL — это современный подход к разработке API, который позволяет клиентам запрашивать только те данные, которые им необходимы. Это делает взаимодействие с API более гибким и эффективным по. . .	Модель полного двоичного сумматора с помощью логических операций (python) AlexSky-coder 04.01.2025 def binSum(x:list, y:list): s=^y] p=x and y for i in range(1,len(x)): s. append((x^y)^p) p=(x and y)or(p and (x or y)) return s x=list() y=list()	Это мы не проходили, это нам не задавали...(асихронный счётчик с управляющим сигналом зад Hrethgir 04.01.2025 Асинхронный счётчик на сумматорах (шестиразрядный по числу диодов на плате, но наверное разрядов будет больше - восемь или шестнадцать, а диоды на старшие), так как триггеры прошли тестирование и. . .

@Yetty 7437 / 5029 / 2892 Регистрация: 18.12.2017 Сообщений: 15,692
	15.07.2019, 04:03	24
	Сообщение от plzvtl в моем примере я начинаю с i+1 скорее всего именно так и нужно. но так как Вы не сообщили результат моего последнего варианта, наверное для Вас это уже не актуально. 0

@plzvtl 57 / 43 / 12 Регистрация: 27.10.2018 Сообщений: 454
	15.07.2019, 04:17 [ТС]	27
	Сообщение от Yetty проверьте Проверил , все еще нет. 0