Поиск и сортировка массивов

Question

Я принимаю вводный уровень C++. Я должен написать булеву функцию, которая проверяет наличие дубликатов вдоль векторов и возвращает истину и ложь, если нет дубликатов

#include<iostream> 
#include<vector> 
using namespace std; 
bool has_duplicates(const vector <int> &v); 


int main() { 

    vector<int> Vec(8); 
    Vec = { 20, 30, 40, 50, 10, 20, 5, 6 }; 
    has_duplicates(Vec); 
    return 0; 
} 
bool has_duplicates(const vector<int>& v) { 
    bool duplicatefound = false; 
    for (int i = 0; i < 8; i++) { // Check each other number in the array 
     for (int j = i; j < 8; j++) { // Check the rest of the numbers 
      while (j != i) {// Makes sure don't check number against itself 
       if (v[i] == v[j]) { 
        cout << "duplicate found" << endl; 
        duplicatefound = true; 
        break; 
       } 
      } 
     } 
    } 
    return duplicatefound; // Reset the boolean after each number entered has been checked 
} 

Answer 1

Там не очень простое решение вашей проблемы:

1. Итерация через массив, с помощью цикла: for(int i=0; i < array_length; i++)

2. в пределах этого цикла, чтобы использовать другую петлю, чтобы проверить, является ли какое-либо значение до одного, к которому i указует, равно your_array[i]. Если это так, вы нашли дубликат и можете return true, иначе петли будут запускаться только до тех пор, пока не будет достигнут конец массива, а затем вы можете return false. Таким образом, ваша целая функция будет что-то вроде:

   bool contains_duplicates(int array[], int len) { 
       for(int i=0; i < len; i++) { 
        for(int j=0; j < i; j++) { 
         if(array[j]==array[i]) { 
          return true; 
         } 
        } 
       } 
   
       return false; 
   } 
   

Надежда Я мог бы помочь, ура!
lindebear

Answer 2

Вы можете использовать шаблоны, чтобы расширять тип, содержащийся на этом векторе. Это решение снижает сложность алгоритма до O (n log n), которое лучше, чем O (n^2), из вашего вложенного цикла, это не значит, что оно будет быстрее всегда, но оно имеет значение для больших векторов.

template< typename T> 
bool hasDuplicates(std::vector<T> vect) { 
    std::sort(vect.begin(), vect.end()); 
    T last; 
    typename vector<T>::iterator it; 
    for(it = vect.begin(); it < vect.end(); it++) { 
     if (vect.begin() != it) { 
      if(last == *it) { 
       return true; 
      } 
     } 
     last = *it; 
    } 
    return false; 
}