Java 470 - Telegram Web

🖥

Задача c собеседования

О единственном дубликате в массиве целых чисел
Задан массив (или ArrayList, как вам больше нравится) целых чисел, в котором содержатся элементы Integer от 1 до 100. В этом массиве есть один и только один продублированный элемент. Как его найти?

Такие задачи для Java-программиста привычнее, чем предыдущие три. Потому что она не о знании тонкостей языка, которые почти никогда не используются, а о логике.

Первый необузданный порыв — решать перебором — пропадает довольно быстро, когда включается голова или там установка «я же программист, я же умный». Плохо только, что на собеседовании, в условиях стресса, этого может и не произойти. Так что думайте сейчас, прежде, чем заглядывать в решение!
Алгоритм решения следующий:
Посчитайте сумму всех чисел от 1 до 100. Думаем, вы знаете, как это можно сделать (например, с помощью знаменитого метода Гаусса)

Теперь считаете сумму элементов вашего массива или ArrayList’а.

И… вычитаете первую сумму из второй.

Бинго! Полученное число — и есть значение дублирующегося элемента.

Код решения java-задачи для ArrayList.

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class FindDuplicate {
    private static void findDuplicate(List<Integer> elements) {
//находим сумму всех уникальных элементов списка
        int distinctSum = elements.stream().distinct().mapToInt(e -> e).sum();
//находим сумму всех элементов списка
        int totalSum = elements.stream().mapToInt(e -> e).sum();
        System.out.println("Элемент, который повторяется : " + (totalSum - distinctSum));
    }

    public static void main(String[] args) {
//создаем список последовательных элементов на промежутке [1..101).
        List <Integer> elements = IntStream.range(1, 101).boxed().collect(Collectors.toList());
//устанавливаем элементу с индексом 53 значение 23
        elements.set(53, 23);
        findDuplicate(elements);
    }
}

Другое решение

import java.util.List;
import java.util.ArrayList;

public class Duplicate {

    public int findDuplicateNumber(List<Integer> numbers) {

        int highestNumber = numbers.size() - 1;
        int total = getSum(numbers);
        int duplicate = total - (highestNumber * (highestNumber + 1) / 2);
        return duplicate;
    }

    public int getSum(List<Integer> numbers) {

        int sum = 0;
        for (int num : numbers) {
            sum = sum + num;
        }
        return sum;
    }

    public static void main(String a[]) {
        List <Integer> numbers = new ArrayList <Integer>();
        for (int i = 1; i < 100; i++) {
            numbers.add(i);
        }
        //добавляем дубликат в список
        numbers.add(25);
        Duplicate dn = new Duplicate();
        System.out.println("Элемент, который повторяется: " + dn.findDuplicateNumber(numbers));
    }
}

@javatg

Please open Telegram to view this post

VIEW IN TELEGRAM

2.1K views11:43