VPF::[Java] количество одинаковых чисел в массиве

Timurkh

Дата 26.11.2011, 21:43 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 26.11.2011

Репутация: нет
Всего: нет

Дан целочисленный массив размера N. Найти количество одинаковых чисел в массиве.

помогите пожалуйста кто может отобразить надо число и количество повторов нельзя использавать sorting.

JurisLacis

Дата 27.11.2011, 01:12 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 26.11.2011

Репутация: нет
Всего: нет

Я новичек в Java, и не знаю на сколько это красиво и правильно, но можно так --

Код


import java.util.ArrayList;

public class IntMatchesArray {
    private static ArrayList<Integer> el = new ArrayList<Integer>();      //чисто для сохранения элементов которые уже были проверены
    public static void main (String[] args) {
        int[] arr = {1, 2, 3, 5, 3, 8, 8, 1, 7, 4, 3, 8, 1, 4, 0, 3, 6, 9};           //пример массива
        int element = 0;                                                                             //сохраняем элемент для вывода
        int count = 0;                                                                                 //сохоаняем колличество совпадений для вывода
        for (int i = 0; i < arr.length; i++) {                                                  //тут считаем элемены
            if (c_element(arr[i])) {
                for (int j = 0; j < arr.length; j ++) {
                    if (arr[i] == arr[j]) {
                        count++;
                        element = arr[j];
                        el.add(arr[i]);
                    }
                }
            }
            if (count > 1) System.out.println("element = " + element + "; match count = " + count);  //если совпадений больше 1 то выводим на экран
            count = 0;                                                                                    //тут сбрасываем счетчик
        }
    }
    private static boolean c_element (int arr_i) {               //тут бует проверка элемента, считали ли мы его?
        for (int k = 0; k < el.size(); k++) {                            
            if (arr_i == el.get(k)) return false;
        }
        return true;
    }
}

jk1

Дата 27.11.2011, 05:31 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 1168
Регистрация: 17.10.2008
Где: Санкт-Петербург

Репутация: 1
Всего: 75

Для домашних заданий, курсовых, существует "Центр Помощи".

Тема перенесена!

--------------------

Opinions are like assholes — everybody has one

Stolzen

Дата 27.11.2011, 07:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: нет
Всего: 48

Если я правильно понял задачу, то вам нужно посчитать количество всех элементов, встречающихся более одного раза.

Код


public class FindDuplicates {
    
    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 5, 3, 8, 8, 1, 7, 4, 3, 8, 1, 4, 0, 3, 6, 9};  
        Map<Integer, Integer> indexed = indexCount(arr);
        int duplicates = countDuplicates(indexed);
        System.out.printf("Количество дубликатов - %d", duplicates);
    }
    
    /**
     * Маппит элемент на количество его повторений во входном массиве.
     */
    public static <E> Map<E, Integer> indexCount(E... arr) {
        Map<E, Integer> index = new HashMap<E, Integer>();
        
        for (E elem : arr) {
            Integer counter = index.get(elem);
            if (counter != null) {
                index.put(elem, counter + 1);
            } else {
                index.put(elem, 1);
            }
        }
        
        return index;
    }
    
    /**
     * Ищет повторения в подготовленном словаре. Повторением считается элемент,
     * который встречается более одного раза.
     */
    public static <E> int countDuplicates(Map<E, Integer> indexed) {
        int count = 0;
        for (Entry<E, Integer> index : indexed.entrySet()) {
            Integer value = index.getValue();
            if (value > 1) {
                count = count + value; 
            }
        }
        return count;
    }

}

Вычисление производится в два этапа - сначала узнаем, сколько повторений в массиве для каждого элемента, затем считаем количество элементов, которые встречаются более одного раза. Решение за O(n).

Тесты:

Код


public class FindDuplicatesTest {
    @Test
    public void testOneOfEach() {
        Map<Integer, Integer> index = FindDuplicates.indexCount(1, 2, 3);
        assertEquals(1, index.get(2).intValue());
    }

    @Test
    public void testGetsIndexed() {
        Map<Integer, Integer> index = FindDuplicates.indexCount(1, 3, 2, 2, 3, 5, 3, 3);
        
        assertEquals(1, index.get(1).intValue());
        assertEquals(4, index.get(3).intValue());
    }
    
    @Test
    public void testCountDuplicates() {
        Map<Integer, Integer> indexed = FindDuplicates.indexCount(1, 3, 2, 2, 3, 5, 3, 3);
        int duplicates = FindDuplicates.countDuplicates(indexed);
        assertEquals(6, duplicates);
    }
}

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »