Algorithms/src/main/java/algorithms/intro/App.java - develop - javapractice/JavaPractice

Algorithms/src/main/java/algorithms/intro/App.java
107 строк4 KB
Zexa91x0
Algorithms - TimSort
15 май 2021, 10:41
15 май 2021, 10:41824af71
package algorithms.intro;

import java.util.HashMap;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself. <br> Given a number, n , determine and print whether it is  Prime  or Not prime.
 * <p>
 * Note: If possible, try to come up with a  primality algorithm, or see what sort of optimizations you come up with for an  algorithm. Be sure to check out the Editorial after submitting your code.
 * <p>
 * <p>
 * O(1) - constant best <br>
 * O (log(n)) - fast<br>
 * O (n) - middle<br>
 * O (n^2) под другому O (n*n) - slow<br>
 */

public class App {

    /**
     * пример алгоритма O (n)
     */
    public static int findNumsOfRepetitions(String s, char c) {
        int sum = 0;

        // это выполняется n раз
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) sum++;
        }

        return sum;
    }

    /**
     * O (n^2) под другому O (n*n)
     */
    public static int[] findNumsOfRepetitions1(String s, char[] c) {

        int[] result = new int[c.length];

        // это выполняется n*n раз
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < c.length; j++) {
                if (s.charAt(i) == c[j]) result[j]++;
            }
        }

        return result;
    }

    /**
     * пример улучшения предыдущего алгоритма до O (n)
     */
    public static int[] findNumsOfRepetitions2(String s, char[] c) {

        int[] result = new int[c.length];

        HashMap<Character, Integer> map = new HashMap<>();

        // это выполняется n раз
        for (int i = 0; i < s.length(); i++) {
            if (!map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), 1);
            } else {
                map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
            }
        }

        for (int i = 0; i < c.length; i++) {
            result[i] = map.getOrDefault(c[i], 0);
        }

        return result;
    }

    public static void main(String[] args) {

        char[] chars = IntStream.rangeClosed('A', 'z') // указываем диапазон символов, тут весь русский алфавит
                .mapToObj(c -> "" + (char) c)
                .collect(Collectors.joining()).toCharArray(); // собираем в массив

        String string = new Random().ints(50000000, 0, chars.length) // рандомно выбираем 5 чисел от 0 до 64
                .mapToObj(i -> String.valueOf(chars[i])). // берем значение из массива
                collect(Collectors.joining()); // склеиваем, можно склеить через разделитель .joining(" ,")

        long startTime = System.nanoTime();
        System.out.print(findNumsOfRepetitions(string, 'A'));
        long endTime = System.nanoTime();
        long duration = endTime - startTime;
        System.out.println("findNumsOfRepetitions " + duration + "ns");

        startTime = System.nanoTime();
        findNumsOfRepetitions1(string, chars);
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("findNumsOfRepetitions1 " + duration + "ns");

        startTime = System.nanoTime();
        findNumsOfRepetitions2(string, chars);
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("findNumsOfRepetitions2 " + duration + "ns");

    }
}