0

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

Входные: 10 5

1 1 3 3 5 7 9 18 18 57

57 3 9 1 179

На выходе должно получиться:

10 10

3 4

7 7

1 2

0

У меня на выходе всё до 1 2 выходит правильно. Почему на этой строчке выход за границы массива? Я же прописал условие.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();

        Integer[] a = new Integer[N];
        Integer[] b = new Integer[M];

        for(int i = 0; i < N; i++){
            a[i] = scanner.nextInt();
        }

        for (int i = 0; i < M; i++) {
            b[i] = scanner.nextInt();
        }



        for (int i = 0; i < M; i++) {
            if (Arrays.binarySearch(a, b[i]) >= 0) {
                int index = Arrays.binarySearch(a, b[i]);
                int f_index = index;
                int l_index = index;
                if (index >= 1) {
                    while(b[i].equals(a[index - 1])) {
                        index--;
                        f_index = index;
                    }
                }
                index = l_index;
                if (index + 1 < M) {
                    while (b[i].equals(a[index + 1])) {
                        if (index + 1 < M) {
                            index++;
                            l_index = index;
                        }
                    }
                }
                System.out.print(f_index + 1 + " ");
                System.out.println(l_index + 1);
            }
            else{
                System.out.println(0);
            }
        }
    }
}

2 ответа 2

0

Тебе нужно проверять на границы массива в цикле каждый раз перед b[i].equals(a[index - 1]) и b[i].equals(a[index + 1]. Предлагаю сделать так:

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();

        Integer[] a = new Integer[N];
        Integer[] b = new Integer[M];

        for(int i = 0; i < N; i++){
            a[i] = scanner.nextInt();
        }

        for (int i = 0; i < M; i++) {
            b[i] = scanner.nextInt();
        }



        for (int i = 0; i < M; i++) {
            if (Arrays.binarySearch(a, b[i]) >= 0) {
                int index = Arrays.binarySearch(a, b[i]);
                int f_index = index;
                int l_index = index;
                while (index >= 1 && b[i].equals(a[index - 1])) {
                    index--;
                    f_index = index;
                }
                index = l_index;
                while (index + 1 < M && b[i].equals(a[index + 1])) {
                    index++;
                    l_index = index;
                }
                System.out.print(f_index + 1 + " ");
                System.out.println(l_index + 1);
            }
            else{
                System.out.println(0);
            }
        }
    }
}
0

Не понятно зачем 2 раза выполнять Arrays.binarySearch, так же не понятно зачем в самих цикла писать f_index = index или l_index = index. Так же можно избавиться от l_index. И да как писал @habibulka нужно проверять границы массива в условии циклов.

int index = Arrays.binarySearch(a, b[i]);
if (index >= 0) {
    while(index >= 1 && b[i].equals(a[index - 1]))
        index--;
    int f_index = index;

    while(index + 1 < M && b[i].equals(a[index + 1]))
        index++;

    System.out.print(f_index + 1 + " ");
    System.out.println(index + 1);
}
else{
    System.out.println(0);
}

P.S. был бы c++ использовал бы функции upper_bound и lower_bound. Их конечно можно реализовать и на Java...

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.