JetBrains Academy: Linear search in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki

JetBrains Academy: Linear search in Java

Does the array contain the element?:

Implement a method to test if an array of int's contains the given number. The array can be empty.

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

public class Main {

    public static boolean contains(int[] numbers, int number) {
        // write your code here
        for (int element : numbers) {
            if (element == number) {
                return true;
            }
        }
        return false;
    }

    /* Do not change code below */
    @SuppressWarnings("Duplicates")
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int[] numbers;
        final int k;
        if (scanner.hasNextInt()) {
            numbers = Arrays.stream(scanner.nextLine().split("\\s+"))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            k = Integer.parseInt(scanner.nextLine());
        } else {
            numbers = new int[0];
            k = 10;
        }
        System.out.println(contains(numbers, k));
    }
}

---

The index of the last occurrence:

Implement a method to search the index of the last occurrence of a given value in an input array of int's.

If the value is not found, the method must return -1.

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

public class Main {

    public static int searchIndexOfLastOccurrence(int[] numbers, int value) {
        // write your code here
        int occurrence = -1;
        
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == value) {
                occurrence = i;
            }
        }
        
        return occurrence;
    }

    /* Do not change code below */
    @SuppressWarnings("Duplicates")
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int[] numbers;
        final int k;
        if (scanner.hasNextInt()) {
            numbers = Arrays.stream(scanner.nextLine().split("\\s+"))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            k = Integer.parseInt(scanner.nextLine());
        } else {
            numbers = new int[0];
            k = 10;
        }
        System.out.println(searchIndexOfLastOccurrence(numbers, k));
    }
}

---

The first occurrence in the subarray:

Implement a method to search the index of the first occurrence of a given value in a range of indexes in a given array. The start index should be inclusive and the end index exclusive. If they are equal, suppose the element is not found.

If the value is not found, the method must return -1.

It's guaranteed that startIndex <= endIndex and the array are not empty.

In the test samples below, the first line represents an array of int's, the second line contains start and end indexes, and the third line has an element to search in the array.

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

public class Main {

    public static int searchInSubArray(int[] numbers, int startIndex, int endIndex, int value) {
        // write your code here
        int occurrence = -1;
        
        for (int i = startIndex; i < endIndex; i++) {
            if (numbers[i] == value) {
                occurrence = i;
                break;
            }
        }
        
        return occurrence;
    }

    /* Do not change code below */
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int[] numbers = Arrays.stream(scanner.nextLine().split("\\s+"))
                .mapToInt(Integer::parseInt)
                .toArray();
        final String[] parts = scanner.nextLine().split("\\s+");
        final int startIndex = Integer.parseInt(parts[0]);
        final int endIndex = Integer.parseInt(parts[1]);
        final int k = Integer.parseInt(scanner.nextLine());
        System.out.println(searchInSubArray(numbers, startIndex, endIndex, k));
    }
}

---

The number of occurrences:

Implement a method to count the number of occurrences of a value in an array of int's.

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

public class Main {

    public static int count(int[] numbers, int value) {
        // write your code here
        int counter = 0;
        for (int number : numbers) {
            if (number == value) {
                counter++;
            }
        }
        return counter;
    }

    /* Do not change code below */
    @SuppressWarnings("Duplicates")
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int[] numbers;
        final int k;
        if (scanner.hasNextInt()) {
            numbers = Arrays.stream(scanner.nextLine().split("\\s+"))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            k = Integer.parseInt(scanner.nextLine());
        } else {
            numbers = new int[0];
            k = 10;
        }
        System.out.println(count(numbers, k));
    }
}

---

The index of the K occurrence:

So you know how to find the first/last occurrence of a value in an array. But what about the second one, the third one and so on?

Your task here is to implement a method to search the index of the K-th occurrence of a given value in an input array of integers. It is guaranteed that K >= 1. If the value is not found, the method must return -1. The input array can be empty.

Input format: The first line contains all elements of the input array separated by spaces. The second line contains only a single number: the value to be found. The last line contains the needed occurrence in the array.

Output format: Your program should output only a single value: the index of the value.

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

public class Main {

    public static int searchIndexOfKOccurence(int[] numbers, int value, int k) {
        // write your code here
        int occurrence = -1;
        int counter = 0;
        
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == value) {
                counter++;
                if (counter == k) {
                    occurrence = i;
                }
            }
        }
        
        return occurrence;
    }

    /* Do not change code below */
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int[] numbers;
        final int k;
        final int value;
        if (scanner.hasNextInt()) {
            numbers = Arrays.stream(scanner.nextLine().split("\\s+"))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            value = Integer.parseInt(scanner.nextLine());
            k = Integer.parseInt(scanner.nextLine());
        } else {
            numbers = new int[0];
            value = 0;
            k = 1;
        }
        System.out.println(searchIndexOfKOccurence(numbers, value, k));
    }
}

---

Search indexes of values in another array:

Implement a method to search the index of the first occurrence of each value from the first array in the second one. If a value is not found in the second array, the index is -1. The method must return an array of indexes the same size as the first array.

Both arrays are not empty; values may repeat in arrays.

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

public class Main {

    public static int[] searchIndexes(int[] first, int[] second) {
        // write your code here
        for (int i = 0; i < first.length; i++) {
            int occurrence = -1;
            int value = first[i];
            
            for (int j = 0; j < second.length; j++) {
                if (second[j] == value) {
                    occurrence = j;
                    break;
                }
            }
            first[i] = occurrence;
        }
        
        return first;
    }

    /* Do not change code below */
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int[] first = Arrays.stream(scanner.nextLine().split("\\s+"))
                .mapToInt(Integer::parseInt)
                .toArray();
        final int[] second = Arrays.stream(scanner.nextLine().split("\\s+"))
                .mapToInt(Integer::parseInt)
                .toArray();
        final String result = Arrays.toString(searchIndexes(first, second))
                .replace(", ", " ")
                .replace("[", "")
                .replace("]", "");
        System.out.println(result);
    }
}

---

Count elements of an array in another one:

Implement a method to search the count of occurrence values from the first array in the second one. The method must return an array of counts with the same size as the first array.

Both arrays are not empty; values may repeat in arrays.

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

public class Main {

    public static int[] countOccurrences(int[] first, int[] second) {
        // write your code here
        for (int i = 0; i < first.length; i++) {
            int counter = 0;
            int value = first[i];
            
            for (int number : second) {
                if (number == value) {
                    counter++;
                }
            }
            
            first[i] = counter;
        }
        return first;
    }

    /* Do not change code below */
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int[] first = Arrays.stream(scanner.nextLine().split("\\s+"))
                .mapToInt(Integer::parseInt)
                .toArray();
        final int[] second = Arrays.stream(scanner.nextLine().split("\\s+"))
                .mapToInt(Integer::parseInt)
                .toArray();
        final String result = Arrays.toString(countOccurrences(first, second))
                .replace(", ", " ")
                .replace("[", "")
                .replace("]", "");
        System.out.println(result);
    }
}

---