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

@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 секунды).
Пожалуйста помогите оптимизировать данный код или придумать другой алгоритм.

@nalbe666 · 14.07.2019, 23:57

C++

int firstDuplicate(std::vector<int>& a) {
    short cnt[106] = { 0 };
    for (auto& it : a) {
        if (++cnt[it] != 1) {
            return it;
        }
    }
    return -1;
}

?

@plzvtl · 15.07.2019, 00:12 **[ТС]**

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

?

Вроде правильно скопипастил.

@nalbe666 · 15.07.2019, 00:17

Возможно, вектор нужно передавать в функцию как в вашем примере по значению, не ссылке. std::vector<int> a
Вижу, ретурн не там, где у меня.

@plzvtl · 15.07.2019, 00:23 **[ТС]**

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

.

///

@nalbe666 · 15.07.2019, 01:12

C++

#include <set>
 
int firstDuplicate(std::vector<int>& a) {
    std::set<int> bset;
    for (auto& it : a) {
        if (!bset.insert(it).second) {
            return it;
        }
    }
    return -1;
}

Тоже самое, но с сетом?

@zayats80888 · 15.07.2019, 01:20

del

@nalbe666 · 15.07.2019, 01:31

Полагаю, второй вариант их устроил. Вот ерунда в том, что

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

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

тут они гарантируют размер самих чисел в массиве от 1 до 105 включительно. Соответственно, в первом варианте нужен массив размером 106. А по факту, в тесте они засунули туда другие числа, от чего выход за пределы массива и ошибки.
Зато резиновый сет справился.

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

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

Вот ерунда в том, что

Посыпаю голову пеплом.
Тут исключительно моя вина, я в тупую скопировал условие и недоглядел за корректностью скопированого.
Там 10^5.

@nalbe666 · 15.07.2019, 01:39

Не по теме:

Загадка разгадана, можно спокойно идти спать :).

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

Не по теме:

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

можно спокойно идти спать :).

может еще 1 оптимизацию?

@Yetty · 15.07.2019, 02:05

plzvtl, а такой вариант проходит тест ?:

C++

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

@plzvtl · 15.07.2019, 02:24 **[ТС]**

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

а такой вариант

вот:

@plzvtl · 15.07.2019, 02:25 **[ТС]**

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

а такой вариант

вот:

@Yetty · 15.07.2019, 02:44

plzvtl, возможно подаётся int - вектор, проверьте с типом int:

C++

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

@plzvtl · 15.07.2019, 02:49 **[ТС]**

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

проверьте с типом int:

вот:

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

на 1 тест больше чем 1 вариант (мой)

@Yetty · 15.07.2019, 03:26

plzvtl, size_t не укладывался в значения, ещё разок проверьте пожалста

C++

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

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

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

/

тоже самое

@Yetty · 15.07.2019, 03:43

plzvtl, по времени ограничение. возможно (не проверял) быстрее будет если j начинать c i:

C++

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

@plzvtl 57 / 43 / 12 Регистрация: 27.10.2018 Сообщений: 454
	15.07.2019, 01:41 [ТС]	11
	Не по теме: Сообщение от nalbe666 можно спокойно идти спать :). может еще 1 оптимизацию? 0

@plzvtl 57 / 43 / 12 Регистрация: 27.10.2018 Сообщений: 454
	15.07.2019, 02:24 [ТС]	13
	Сообщение от Yetty а такой вариант вот: 0

@plzvtl 57 / 43 / 12 Регистрация: 27.10.2018 Сообщений: 454
	15.07.2019, 02:49 [ТС]	16
	Сообщение от Yetty проверьте с типом int: вот: Миниатюры 0

@plzvtl 57 / 43 / 12 Регистрация: 27.10.2018 Сообщений: 454
	15.07.2019, 00:12 [ТС]	3
	Сообщение от nalbe666 ? Вроде правильно скопипастил. Миниатюры 0

@nalbe666 863 / 513 / 215 Регистрация: 19.01.2019 Сообщений: 1,216
	15.07.2019, 00:17	4
	Возможно, вектор нужно передавать в функцию как в вашем примере по значению, не ссылке. std::vector<int> a Вижу, ретурн не там, где у меня. 0

@plzvtl 57 / 43 / 12 Регистрация: 27.10.2018 Сообщений: 454
	15.07.2019, 00:23 [ТС]	5
	Сообщение от nalbe666 . /// Миниатюры 0

@zayats80888 6340 / 3511 / 1427 Регистрация: 07.02.2019 Сообщений: 8,977
	15.07.2019, 01:20	7
	del 0

@nalbe666 863 / 513 / 215 Регистрация: 19.01.2019 Сообщений: 1,216
	15.07.2019, 01:31	8
	Полагаю, второй вариант их устроил. Вот ерунда в том, что Сообщение от plzvtl Guaranteed constraints: 1 ≤ a.length ≤ 105, 1 ≤ a[i] ≤ a.length. тут они гарантируют размер самих чисел в массиве от 1 до 105 включительно. Соответственно, в первом варианте нужен массив размером 106. А по факту, в тесте они засунули туда другие числа, от чего выход за пределы массива и ошибки. Зато резиновый сет справился. 0

@plzvtl 57 / 43 / 12 Регистрация: 27.10.2018 Сообщений: 454
	15.07.2019, 01:37 [ТС]	9
	Сообщение от nalbe666 Вот ерунда в том, что Посыпаю голову пеплом. Тут исключительно моя вина, я в тупую скопировал условие и недоглядел за корректностью скопированого. Там 10^5. 0

@nalbe666
	15.07.2019, 01:39 #10
	Не по теме: Загадка разгадана, можно спокойно идти спать :). 0

@plzvtl 57 / 43 / 12 Регистрация: 27.10.2018 Сообщений: 454
	15.07.2019, 02:25 [ТС]	14
	Сообщение от Yetty а такой вариант вот: Миниатюры 0

@plzvtl 57 / 43 / 12 Регистрация: 27.10.2018 Сообщений: 454
	15.07.2019, 03:22 [ТС]	17
	на 1 тест больше чем 1 вариант (мой) 0

@plzvtl 57 / 43 / 12 Регистрация: 27.10.2018 Сообщений: 454
	15.07.2019, 03:30 [ТС]	19
	Сообщение от Yetty / тоже самое Миниатюры 0

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

Решение