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

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

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

Для решения задачи :
"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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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++
1
2
3
4
5
6
7
8
9
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

проверьте

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

Новые блоги и статьи Все статьи Все блоги /
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .

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

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

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