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...

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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