新・アルゴリズムとデータ構造入門 Java編9:数列の k 番目

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

public class Main {
    static int lowerBound(int[] a, int n, int x) {

        int left = 0, right = n;

        while (left != right) {
            int mid = (left + right) / 2;

            if (a[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    static int upperBound(int[] a, int n, int y) {

        int left = 0, right = n;

        while (left != right) {
            int mid = (left + right) / 2;

            if (a[mid] > y) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

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

        int n = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        int m = sc.nextInt();

        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }

        int k = sc.nextInt();

        // 配列 b を昇順にソート

        // 変数 left, right をそれぞれ -1 と 2000000000 で初期化

        // left と right の差が 1 でない間
        // 変数 mid に (left + right) / 2 を代入

        // 個数を表す変数 count を 0 で初期化
        // i を 0 から n - 1 まで繰り返す
        // upperBound(b, m, a[i] + mid) - lowerBound(b, m, a[i] - mid) を count に加算

        // もし count が k 以上なら
        // right を mid で更新
        // そうでなければ
        // left を mid で更新

        // right を出力
    }
}

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

public class Main {
    static int lowerBound(int[] a, int n, int x) {

        int left = 0, right = n;

        while (left != right) {
            int mid = (left + right) / 2;

            if (a[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    static int upperBound(int[] a, int n, int y) {

        int left = 0, right = n;

        while (left != right) {
            int mid = (left + right) / 2;

            if (a[mid] > y) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

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

        int n = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        int m = sc.nextInt();

        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }

        int k = sc.nextInt();

        // 配列 b を昇順にソート

        // 変数 left, right をそれぞれ -1 と 2000000000 で初期化

        // left と right の差が 1 でない間
        // 変数 mid に (left + right) / 2 を代入

        // 個数を表す変数 count を 0 で初期化
        // i を 0 から n - 1 まで繰り返す
        // upperBound(b, m, a[i] + mid) - lowerBound(b, m, a[i] - mid) を count に加算

        // もし count が k 以上なら
        // right を mid で更新
        // そうでなければ
        // left を mid で更新

        // right を出力
    }
}

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

public class Main {
    static int lowerBound(int[] a, int n, int x) {

        int left = 0, right = n;

        while (left != right) {
            int mid = (left + right) / 2;

            if (a[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    static int upperBound(int[] a, int n, int y) {

        int left = 0, right = n;

        while (left != right) {
            int mid = (left + right) / 2;

            if (a[mid] > y) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

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

        int n = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        int m = sc.nextInt();

        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }

        int k = sc.nextInt();

        // ここにコードを書く
    }
}

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

public class Main {
    static int lowerBound(int[] a, int n, int x) {

        int left = 0, right = n;

        while (left != right) {
            int mid = (left + right) / 2;

            if (a[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    static int upperBound(int[] a, int n, int y) {

        int left = 0, right = n;

        while (left != right) {
            int mid = (left + right) / 2;

            if (a[mid] > y) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

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

        int n = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        int m = sc.nextInt();

        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }

        int k = sc.nextInt();

        // ここにコードを書く
    }
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1

問題ログインすると模範解答や入力を見ることができます

演習課題「k 番目の値」

整数 n, m, k と長さ n の配列 a, 長さ m の配列 b が与えられるので、各 i, j に対して a[i] - b[j] で表される合計 n × m 個の整数のうち、小さい方から k 番目の値を求めてください。
すでに入力を行うコードと関数 lowerBound, upperBound が実装されているので、コードを書き足して完成させてください。

入力される値

5
1 2 3 4 5
3
1 2 3
3

標準入力からの値取得方法はこちらをご確認ください

期待する出力値

-3

Tips

動画へ戻る

次のレッスンへ前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃07:数列の k 番目

レベルアップ問題集「二分探索メニュー」の「長い長い数列」の問題を解いていきます。

プログラミング学習 > 新・アルゴリズムとデータ構造入門 Java編 > 新・アルゴリズムとデータ構造入門 Java編9: 二分探索 > 数列の k 番目

ログインすると採点できます

コードの実行

有料会員になるとエンジニアに質問ができます

出力タイプ：