Untitled

package com.example.task6_6;

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

public class LogicProgram {
    public static void main(String[] args) {
        int[] num = {2, 2, 1, 1};
        Map<Integer, List<Integer>> positions = buildPositionsMap(num);
        int maxFreqNum = findMostFrequentNumber(positions);
        printResult(maxFreqNum, positions.get(maxFreqNum));
    }

    // Метод для создания отображения чисел и их позиций в массиве
    public static Map<Integer, List<Integer>> buildPositionsMap(int[] nums) {
        // Создаем словарь отображение для хранения чисел и позиций
        Map<Integer, List<Integer>> positions = new MyHashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            // Если число не существует в отображении, добавляем его со списком позиций
            if (!positions.containsKey(num)) {
                positions.put(num, new ArrayList<>());
            }
            // Добавляем текущую позицию числа в список позиций
            positions.get(num).add(i);
        }

        quickSort(nums, 0, nums.length - 1); // Сортировка массива nums

        return positions;
    }

    // Метод для нахождения наиболее часто встречающегося числа
    public static int findMostFrequentNumber(Map<Integer, List<Integer>> positions) {
        int maxFreqNum = 0;
        int maxFreq = 0;
        for (Map.Entry<Integer, List<Integer>> entry : positions.entrySet()) { // проходимся по всем числам
            int num = entry.getKey(); // Текущее число
            List<Integer> posList = entry.getValue(); // Список позиций для текущего числа
            int freq = posList.size(); // Частота текущего числа (количество позиций)
            if (freq > maxFreq) {
                // Если частота текущего числа больше наибольшей частоты,
                // обновляем наибольшую частоту и число с наибольшей частотой
                maxFreq = freq;
                maxFreqNum = num;
            } else if (freq == maxFreq && num > maxFreqNum) {
                // Если есть другое число с такой же частотой, выбираем наибольшее число
                maxFreqNum = num;
            }
        }
        return maxFreqNum; // Возвращаем число с наибольшей частотой
    }

    // Метод для вывода результата
    private static void printResult(int number, List<Integer> positions) {
        System.out.println("Наиболее часто встречающееся число: " + number);
        System.out.println("Позиции этого числа: " + positions);
    }

    // Метод для выполнения быстрой сортировки массива
    private static void quickSort(int[] num, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(num, low, high);
            quickSort(num, low, pivotIndex - 1); // Рекурсивная сортировка левой части массива
            quickSort(num, pivotIndex + 1, high); // Рекурсивная сортировка правой части массива
        }
    }

    // Метод для разделения массива и выбора опорного элемента
    private static int partition(int[] num, int low, int high) {
        int pivot = num[high]; // Выбираем последний элемент в качестве опорного
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (num[j] <= pivot) {
                i++;
                swap(num, i, j); // Меняем элементы местами
            }
        }
        swap(num, i + 1, high); // Помещаем опорный элемент на правильную позицию
        return i + 1; // Возвращаем индекс опорного элемента
    }

    // Метод для обмена элементов в массиве
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}