Как проверить массив на наличие дублей

Материал из Поле цифровой дидактики
Описание Как проверить массив на наличие дублей? Здесь приводятся решения на нескольких языках высокого уровня - JavaScript, Python, C++, NetLogo, Snap!
Область знаний Информатика
Область использования (ISTE) Computational Thinker
Возрастная категория 10


Поясняющее видео
Близкие рецепту понятия Сортировка
Среды и средства для приготовления рецепта: Snap!, JavaScript, Python

Описание проблемы

У нас есть массив элементов и мы хотим узнать, встречаются ли в нём повторяющиеся элементы

Сравнение

JS Snap!
const hasDuplicates = function (num) {
    //loop the list, our O(n) op
    for (let i = 0; i < nums.length; i++) {
        const thisNum = nums[i];
        //loop the list again, the O(n^2) op
        for (let j = 0; j < nums.length; j++) {
            //make sure we're not checking same number
            if (j !== i) {
                const otherNum = nums[j];
                //if there's an equal value, return
                if (otherNum === thisNum) return true;
            }
        }
    }
    return false;
}
const nums = [1, 2, 3, 4, 5, 5];
hasDuplicates(nums);//true

Has dublicate.png



JavaScript

Вариант 1 - вложенный цикл

const hasDuplicates = function (num) {
    //loop the list, our O(n) op
    for (let i = 0; i < nums.length; i++) {
        const thisNum = nums[i];
        //loop the list again, the O(n^2) op
        for (let j = 0; j < nums.length; j++) {
            //make sure we're not checking same number
            if (j !== i) {
                const otherNum = nums[j];
                //if there's an equal value, return
                if (otherNum === thisNum) return true;
            }
        }
    }
    return false;
}
const nums = [1, 2, 3, 4, 5, 5];
hasDuplicates(nums);//true

Вариант 2 - Двоичный поиск

const nums = [1, 2, 3, 4, 5];
const searchFor = function (items, num) {
}
const hasDuplicates = function (nums) {
    for (let num of nums) {

        if (searchFor(nums, num)) {
            return true;
        }
    }
    return false;
}