Подсчитайте другой элемент массива

Question

Я ИТ-студент, и у нас будет программный экзамен, где тестовая программа проверит нашу программу. Один из examp частиц является то, что мы получаем возраст и зарплату народов, мы должны подсчитать, сколько гладкошерстных возраста люди

Мой код выглядит следующим образом структу:

struct input 
{ 
    int emp_age, emp_paid; 
}; 

И это код , п представляет число всех людей

int diff_sum (int n, input* t) 
{ 
    int uniq_num = n; 

    for(int i = 0; i < n; i++) 
     { 
      for(int j = i; j < n; j++) 
       { 
        if((t[j].emp_age == t[i].emp_age) && (i!=j)) 
         { 
          uniq_num = uniq_num - 1; 
         } 
       } 
     } 
    cout << uniq_num << endl; 
    return 0; 
} 

программа испытаний в 10 раз, а некоторые из упомянутых из положить это хорошо, но в течение некоторого испытания он сказал, что это неправильно из пут. Я не знаю, как работает тестовый движок, и я также не знаю, какова проблема.

Answer 1

One возможность было бы добавить все элементы в контейнере STL с уникальными значениями:

int diff_sum (int n, input* t) 
{ 
    std::set<int> ages; 
    for(int i = 0; i < n; i++) 
     ages.insert(t[i].emp_age); 

    return ages.size(); 
} 

Answer 2

Рассмотрите это: 10 10 10. Подумайте i и j как указание на элементы:

uniq_num = 3 
10 10 10 
i j => uniq_num = 2 

10 10 10 
i  j => uniq_num = 1 

10 10 10 
    i j => uniq_num = 0!!!! 

Итак, мы видим, что во второй внешней итерации, мы сравниваем два числа, которые мы уже известны такие же. Они уже косвенно сравниваются.

Предполагая, что вам не разрешено использовать какие-либо стандартные библиотеки (если да, то почему бы вам не быть? Это было бы тривиально с std::set!), Я работал бы в противоположном порядке.

• Начинается с unique=0.
• Посмотрите на первый элемент. Инкрементный счет.
• Посмотрите на следующий элемент. Сравните его со всеми предыдущими элементами. Если они не совпадают, счетчик увеличивается.
• Повторите.

(Имейте в виду, что это не самый лучший алгоритм, а не то, что я хотел бы сделать для больших входов, но это довольно просто объяснить и реализовать с использованием самых основных C++ понятий.)

Answer 3

Алгоритм:

1. Найти минимальный и максимальный возраст (назовем их min_age и max_age)

2. Выделяют массив с MAX_AGE-min_age + 1 записей (назовем его age_arr)

3. Установите все записи в age_arr до 0

4. Для каждой структуры x, установите 1 в позиции # x.emp_age-min_age

5. Сумма всех значений (0s или 1s) в age_arr, удалить age_arr и возвращает результат

Реализация:

//Phase 1 
int min_age = 1000; // Assumption!!! 
int max_age = 0; // Assumption!!! 
for(int i=0; i<n; i++) 
{ 
    if (min_age > t[i].emp_age) 
     min_age = t[i].emp_age; 
    if (max_age < t[i].emp_age) 
     max_age = t[i].emp_age; 
} 

//Phase 2 
int age_arr_size = max_age-min_age+1; 
int age_arr[] = new int[age_arr_size]; 

//Phase 3 
for(int age=0; age<age_arr_size; age++) 
    age_arr[age] = 0; 

//Phase 4 
for(int i=0; i<n; i++) 
    age_arr[t[i].emp_age-min_age] = 1; 

//Phase 5 
int age_count = 0; 
for(int age=0; age<age_arr_size; age++) 
    age_count += age_arr[age]; 
delete[] age_arr; 
return age_count; 

Answer 4

Проблема заключается в том, что ваш код будет недооценивать число уникальных возрастов:

eg говорят, что возрасты {1,2,3,4,1,5,6,1,7}

Очевидно, что есть 7 уникальных возрастов здесь, и п = 9.

В вашем коде только время uniq_num будет уменьшено, когда i = 0 (когда uniq_num уменьшается на 2) и i = 4 (когда uniq_num уменьшается на другое 1).

Последний случай двойной счет, так что ваш алгоритм дает ответ 6 вместо 7.