Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
51 / 41 / 9
Регистрация: 27.10.2018
Сообщений: 426
1

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

14.07.2019, 23:25. Просмотров 1369. Ответов 26
Метки нет (Все метки)

Для решения задачи :
"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 секунды).
Пожалуйста помогите оптимизировать данный код или придумать другой алгоритм.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.07.2019, 23:25
Ответы с готовыми решениями:

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

Оптимизировать код
Первое число входного потока - количество чисел Дальше идут те самые числа Надо найти кол-во пар...

Оптимизировать код
Для решения задачи : &quot;Note: Write a solution that only iterates over the string once and uses...

Как оптимизировать код
Доброй ночи господа у меня к вам такая просьба как можно упростить данный код? #include &lt;iostream&gt;...

26
676 / 429 / 180
Регистрация: 19.01.2019
Сообщений: 1,011
14.07.2019, 23:57 2
C++
1
2
3
4
5
6
7
8
9
int firstDuplicate(std::vector<int>& a) {
    short cnt[106] = { 0 };
    for (auto& it : a) {
        if (++cnt[it] != 1) {
            return it;
        }
    }
    return -1;
}
?
0
51 / 41 / 9
Регистрация: 27.10.2018
Сообщений: 426
15.07.2019, 00:12  [ТС] 3
Цитата Сообщение от nalbe666 Посмотреть сообщение
?
Вроде правильно скопипастил.
0
Миниатюры
Оптимизировать код  
676 / 429 / 180
Регистрация: 19.01.2019
Сообщений: 1,011
15.07.2019, 00:17 4
Возможно, вектор нужно передавать в функцию как в вашем примере по значению, не ссылке. std::vector<int> a
Вижу, ретурн не там, где у меня.
0
51 / 41 / 9
Регистрация: 27.10.2018
Сообщений: 426
15.07.2019, 00:23  [ТС] 5
Цитата Сообщение от nalbe666 Посмотреть сообщение
.
///
0
Миниатюры
Оптимизировать код  
676 / 429 / 180
Регистрация: 19.01.2019
Сообщений: 1,011
15.07.2019, 01:12 6
Лучший ответ Сообщение было отмечено plzvtl как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
#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;
}
Тоже самое, но с сетом?
1
3528 / 1980 / 832
Регистрация: 07.02.2019
Сообщений: 5,309
15.07.2019, 01:20 7
del
0
676 / 429 / 180
Регистрация: 19.01.2019
Сообщений: 1,011
15.07.2019, 01:31 8
Полагаю, второй вариант их устроил. Вот ерунда в том, что
Цитата Сообщение от plzvtl Посмотреть сообщение
Guaranteed constraints:
1 ≤ a.length ≤ 105,
1 ≤ a[i] ≤ a.length.
тут они гарантируют размер самих чисел в массиве от 1 до 105 включительно. Соответственно, в первом варианте нужен массив размером 106. А по факту, в тесте они засунули туда другие числа, от чего выход за пределы массива и ошибки.
Зато резиновый сет справился.
0
51 / 41 / 9
Регистрация: 27.10.2018
Сообщений: 426
15.07.2019, 01:37  [ТС] 9
Цитата Сообщение от nalbe666 Посмотреть сообщение
Вот ерунда в том, что
Посыпаю голову пеплом.
Тут исключительно моя вина, я в тупую скопировал условие и недоглядел за корректностью скопированого.
Там 10^5.
0
nalbe666
15.07.2019, 01:39
  #10

Не по теме:

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

0
51 / 41 / 9
Регистрация: 27.10.2018
Сообщений: 426
15.07.2019, 01:41  [ТС] 11

Не по теме:

Цитата Сообщение от nalbe666 Посмотреть сообщение
можно спокойно идти спать :).
может еще 1 оптимизацию?


0
4772 / 3248 / 1957
Регистрация: 18.12.2017
Сообщений: 10,365
15.07.2019, 02:05 12
plzvtl, а такой вариант проходит тест ?:
C++
1
2
3
4
5
6
7
8
9
10
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;
}
0
51 / 41 / 9
Регистрация: 27.10.2018
Сообщений: 426
15.07.2019, 02:24  [ТС] 13
Цитата Сообщение от Yetty Посмотреть сообщение
а такой вариант
вот:
0
51 / 41 / 9
Регистрация: 27.10.2018
Сообщений: 426
15.07.2019, 02:25  [ТС] 14
Цитата Сообщение от Yetty Посмотреть сообщение
а такой вариант
вот:
0
Миниатюры
Оптимизировать код  
4772 / 3248 / 1957
Регистрация: 18.12.2017
Сообщений: 10,365
15.07.2019, 02:44 15
plzvtl, возможно подаётся int - вектор, проверьте с типом int:
C++
1
2
3
4
5
6
7
8
9
10
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;
}
0
51 / 41 / 9
Регистрация: 27.10.2018
Сообщений: 426
15.07.2019, 02:49  [ТС] 16
Цитата Сообщение от Yetty Посмотреть сообщение
проверьте с типом int:
вот:
0
Миниатюры
Оптимизировать код  
51 / 41 / 9
Регистрация: 27.10.2018
Сообщений: 426
15.07.2019, 03:22  [ТС] 17
на 1 тест больше чем 1 вариант (мой)
0
4772 / 3248 / 1957
Регистрация: 18.12.2017
Сообщений: 10,365
15.07.2019, 03:26 18
plzvtl, size_t не укладывался в значения, ещё разок проверьте пожалста
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 = 0; j < n; j++)
        if (i!=j && a[i]==a[j]) {n=j;value=a[i];break;}
    return value;
}
0
51 / 41 / 9
Регистрация: 27.10.2018
Сообщений: 426
15.07.2019, 03:30  [ТС] 19
Цитата Сообщение от Yetty Посмотреть сообщение
/
тоже самое
0
Миниатюры
Оптимизировать код  
4772 / 3248 / 1957
Регистрация: 18.12.2017
Сообщений: 10,365
15.07.2019, 03:43 20
plzvtl, по времени ограничение. возможно (не проверял) быстрее будет если j начинать c i:
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; j < n; j++)
        if (i!=j && a[i]==a[j]) {n=j;value=a[i];break;}
    return value;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.07.2019, 03:43

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Оптимизировать и минимализировать код
Cделал легкую прогу. Понимаю логики 0 в коде. Можете помочь оптимизировать код? А заодно и сделать...

Нужно оптимизировать код
Гистограмма является многоугольником, сформированным из последовательности прямоугольников,...

Как оптимизировать код?
Вот такой код, написанный для микроконтроллера импульсного блока питания. Просто интересно мнение,...

Нужно оптимизировать код
Нужно максимально сократить код #include &lt;iostream&gt; using namespace std; int main(int...

Помогите оптимизировать код
Здравствуйте! Помогите, пожалуйста, оптимизировать его: main.cpp #include &quot;main.h&quot;...

Как оптимизировать код?
Как оптимизировать код, чтобы работала программа быстрее #include &lt;iostream&gt; #include &lt;fstream&gt;...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.