Программа для поиска большинства элементов входного массива не работает - PullRequest
Новая
       35

Программа для поиска большинства элементов входного массива не работает

0 голосов
/ 05 сентября 2018

Я пытаюсь найти элемент большинства, используя подход Бойера и Мура. Программа должна попросить пользователя ввести «n» количество строк в первой строке, тогда после ввода «n» будет следовать число «n» строк. (Пример: пользовательский ввод 5 в первой строке, затем будет 5 цифр) Затем используйте подход Бойера и Мура, чтобы найти элемент большинства входного массива. Если мажоритарный элемент не существует во входном массиве, выполните -1. Мой вывод программы показывает 0 независимо от того, какой ввод я ввел. Не могли бы вы проверить это и исправить мою программу?

Пример вывода: 4 12 12 1 12 12 / Или: 3 11 2 13 -1 

public static void main (String[]args)
{
    int a[] = new int [1000000];
    Scanner sc = new Scanner (System.in);

    // User input n number of lines
    int numberOfLine = sc.nextInt();

    //Loop to have n elements as input
    for (int i = 1; i<= numberOfLine; i++)
    {
        a[i] = sc.nextInt();
    }

    // Call method to display majority element
    getMajorityElement(a);
    sc.close();
}       

//Method to Find M.E using Boyer & Moore approach
public static void getMajorityElement(int [] array)
{
    int majorityElement = array[0];
    int count = 1;
    for (int index = 1; index<array.length; index++)
    {
        if(majorityElement==array[index])
        {
            count++;
        }
        else if(count==0)
        {
            majorityElement = array[index];
            count = 1;
        }
        else 
        {
            count --;
        }
    }

    // Check if candidate M.E occur more than n/2 times
    count = 0;
    for (int index = 0; index<array.length; index++)
    {
        if(array[index]==majorityElement)
            {
            count++;
            }
    }
        if (count > array.length/2)
        {
        System.out.println(majorityElement);
        }
        else
        {
        System.out.println("-1");
        }
}

1 Ответ

0 голосов
/ 05 сентября 2018

Причина, по которой вы получаете такое поведение, состоит в том, что в вашем массиве из 1 000 000 элементов элемент большинства равен нулю: установлены только первые три или четыре элемента, а остальные элементы заняты нулями - значение по умолчанию int на Java.

Исправьте эту проблему, выделив размер после ввода длины. Вам также необходимо исправить код, который читает ввод, чтобы убедиться, что данные заканчиваются на индексах 0..numberOfLine-1: 

Scanner sc = new Scanner (System.in);
// User input n number of lines
int numberOfLine = sc.nextInt();
int a[] = new int [numberOfLine];
//Loop to have n elements as input
for (int i = 0 ; i < numberOfLine ; i++) {
    a[i] = sc.nextInt();
}
...