sonia jessica21 июня 2022 г. 3:34

Java-программы для работы с массивами

Массивы в java:

  • Массив — это базовая структура данных, которая содержит элементы схожих типов данных.
  • Всегда есть порядок среди позиций элемента.
  • Доступ к нему можно получить с помощью индексов. Java поддерживает массивы с нулевым индексом. Означает, что индекс массива начинается с 0 в java.
  • Мы можем объявить массив в java как-
    1.int[] arr = new int[size];
    2.int[] arr = {1,2,3…};
    3.int[] arr = new int[]{1,2,3,...};

В этой статье мы рассмотрим некоторые программы с массивами Java для интервью, которые чаще всего задают на собеседовании по Java.

Java-программы для работы с массивами

1. Дан массив arr размера n. Ваша задача — создать выходной массив на основе входного массива, а элементы будут произведением всех элементов входного массива, кроме значения по текущему индексу.
Пример -
обр = [4, 9, 6, 8] вывод = [432, 192, 288, 216]
Объяснение -
При индексе 0 умножение всех элементов, кроме 4, равно - (9 * 6 * 8) = 432.
В индексе 1 умножение всех элементов, кроме 9, равно - (4 * 6 * 8) = 192.
При индексе 2 умножение всех элементов, кроме 6, равно - (4 * 9 * 8) = 288.
В индексе 3 умножение всех элементов, кроме 8, равно - (4 * 9 * 6) = 216.

Решение -

Подход 1 (Brute Force)

import java.util.Arrays;
class Main {
    public static void main(String args[]) {
        int[] arr = {4, 9, 6, 8};
        int[] output = new int[arr.length];
        for(int i = 0; i < arr.length; i++){
            int mul = 1;
            //Loop for multiplying the values of the array.
            for(int j = 0; j < arr.length; j++){
                //Skipping the element for the current index 
                if(i == j)
                    continue;
                mul *= arr[j];
            }
            //Assigning the values to the current index
            output[i] = mul;
        }
        //Printing the output array.
        System.out.print(Arrays.toString(output));
    }
}

В этом подходе мы присваиваем значения выходному массиву для текущего индекса. И каждый раз мы вычисляем значение, которое нужно присвоить конкретному индексу. Этот подход занимает O (n ^ 2) времени. Потому что для каждого индекса мы вычисляем результат.

Подход 2 (Optimized)

import java.util.Arrays;
class Main {
    public static void main(String args[]) {
        int[] arr = {9,6,7,8};
        int[] output = new int[arr.length];
        int multiply = 1;

        //Calculating the multiplication of all the elements.
        for(int n : arr)
            multiply *= n;

        //Assigning to the output array after diving with the
        //elements from input array.
        for(int i = 0; i < arr.length; i++)
            output[i] = multiply / arr[i];

        //Printing the output array.
        System.out.println(Arrays.toString(output));
    }
}

В этом подходе мы сначала вычисляем умножение всех элементов, а затем присваиваем значения выходной переменной путем деления ее на текущий индексированный элемент. Так мы избегаем повторения работы. И нам нужно всего 2 отдельных обхода цикла. Таким образом, временная сложность будет O (n).

2. Напишите программу Java для перемещения всех 0 в конец массива.
Пример -
приб = [8, 0, 0, 7, 3, 0, 2] вывод = [8, 7, 3, 2, 0, 0, 0]
Объяснение -
В индексе 1 есть 0. Таким образом, 0 будет перемещен в последний, а первый ненулевой элемент попадет в 1-й индекс.
Аналогично для индекса 2 и 5 также.

Решение -

Подход (using auxiliary array)

import java.util.Arrays;
class Main {
    public static void main(String args[]) {
        int[] arr =  {8, 0, 0, 7, 3, 0, 2};
        int[] output = new int[arr.length];

        //Pointer for adding the value in the output array.
        int k = 0;
        for(int i = 0; i < arr.length; i++){
            //Skipping the element if it is 0.
            if(arr[i] == 0)
                continue;

            //Assigning the next value to the output variable.
            output[k] = arr[i];
            k++;
        }
        //Printing the output.
        System.out.print(Arrays.toString(output));
    }
}

В приведенном выше подходе мы создаем дополнительный массив и добавляем к нему ненулевое значение, чтобы оставшееся пространство в массиве заполнялось 0. Временная сложность этого подхода составляет O (n), а пространственная сложность также равна O. (н).

Подход 2 (используя 2 указателя) -

import java.util.Arrays;
class Main {
    public static void main(String args[]) {
        int[] arr =  {8, 0, 0, 7, 3, 0, 2};
        int i = 0, j = 0;

        while(i < arr.length){
            //if find 0 then continue until nonzero found.
            if(arr[i] == 0){
                i++;
            }else{
                //Swapping the values of 1st non-zero number found after 0
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
                i++;
                j++;
            }
        }
        //Printing the output.
        System.out.print(Arrays.toString(arr));
    }
}

В приведенном выше коде мы взяли 2 указателя. Один будет указывать на следующий 0, который нужно отправить последним, а другой будет следующим элементом, который заменит индекс первого указателя. Временная сложность этого будет O(n), а пространственная сложность будет постоянной O(1).

3. Напишите программу на Java для печати массива, содержащего лидеров из заданного входного массива. Лидером является элемент, у которого все элементы справа меньше его.
Пример -
приб = [8, 2, 5, 7, 3, 4, 2] вывод = [2, 4, 7, 8]
Объяснение -
Мы видим, что 2 является лидером, потому что 2 является последним элементом в массиве. 4 также является лидером, потому что после 4 все элементы меньше этого. И так же 7 и 8 тоже.

Решение -
Подход 1 (Brute force)

import java.util.ArrayList;
class Main {
    public static void main(String args[]) {
        int[] arr = {8, 2, 5, 7, 3, 4, 2};
        //Creating ArrayList that will contain the leader elements.
        ArrayList<Integer> ans = new ArrayList<>();

        for(int i = 0; i < arr.length; i++){
            boolean flag = true;

            //Checking if the particular element is the leader.
            for(int j = i+1; j < arr.length; j++){

                //If it's not the leader then changing the flag to false 
                //and break
                if(arr[j] > arr[i]){
                    flag = false;
                    break;
                }
            }
            //if flag is not false then we know that the element is the 
            //leader adds in the answer.
            if(flag)
                ans.add(arr[i]);
        }
        //Printing the answer.
        System.out.println(ans);
    }
}

В приведенном выше подходе мы проверяем каждый элемент, является ли он лидером или нет. Таким образом, временная сложность для описанного выше подхода будет O(n2).

Подход 2 (оптимизированный)-

import java.util.ArrayList;
class Main {
    public static void main(String args[]) {
        int[] arr = {8, 2, 5, 7, 3, 4, 2};

        //Declaring Result array to store the leader element
        ArrayList<Integer> ans = new ArrayList<>();

        //n represents the length of array size and max will 
        //store the last element of the array.
        int n = arr.length, max = arr[n-1];
        ans.add(max);
        for(int i = n-2; i >= 0; i--){
            //If found another leader then changing the leader
            //and add to the answer array.
            if(arr[i] > max){
                ans.add(arr[i]);
                max = arr[i];
            }
        }
        //Printing the leader array.
        System.out.print(ans);
    }
}

В этом подходе мы проверяем лидера элемента и находим наибольший. Потому что это будет лидер, так как все меньшие элементы находятся с правой стороны от него. Таким образом, временная сложность для этого подхода составляет O (n).

4. Напишите программу Java, чтобы найти индекс элемента пика в массиве. Пиковый элемент больше, чем его левый и правый элементы.
Пример -
обр = [4, 5, 7, 1, 2, 3] вывод = 2
Объяснение -
Мы видим, что элемент с индексом 2 = (7) больше, чем слева и справа. Элемент (5 и 1).

Решение -

class Main {
    private static int findPeak(int[] arr, int low, int high){
        if(high == low) // Corner case when only a single element is present.
        return low;
        while(low < high){
            //calculating the mid index                                     
            int mid = (low + high) / 2;

            //checking if the element of mid+1 is the peak
            if (mid < high && arr[mid] > arr[mid + 1])
                return mid;

            //checking if the element of mid-1 is the peak
            else if (mid > low && arr[mid] < arr[mid - 1])
                return (mid - 1);

            //checking if element exists on the left side of array from mid then 
            //search on left side
            else if (arr[low] >= arr[mid])
                high = mid - 1;

            //checking if element exists on right side of array from mid 
            //then search on right
            else 
                low = mid + 1;
        }
        return -1; // returning -1 if element is completely sorted
    }
    public static void main(String args[]) {
        int[] arr = {4, 5, 7, 1, 2, 3};
        int peak = findPeak(arr, 0, arr.length-1);
        System.out.print(peak);
    }
}

5. Дан массив из n элементов, в котором каждый элемент встречается не менее 2 раз, кроме одного элемента. Поэтому напишите программу на Java, чтобы найти этот элемент.
Пример -
обр = [2,6,8,5,6,7,1,2,5,6,1,1,9,8,9] Выход = 7
Объяснение -
В приведенном выше массиве только 7 — это элемент, который встречается только один раз, поэтому выведите этот элемент.

Решение -

import java.util.*;
class Main {
    public static void main(String args[]) {
        HashMap<Integer, Integer> hm = new HashMap<>();
        int[] arr = {2,6,8,5,6,7,1,2,5,6,1,1,9,8,9};

        //loop to count the frequency of the element in the array.
        for(int i : arr){
            Object val = hm.get(i);
            if(val == null)
                val = 0;

            //If an element exists then increasing its frequency.
            hm.put(i, (int)val+1);
        }
        for (Map.Entry mapElement : hm.entrySet()) {
            int value = (int)mapElement.getValue();
            //If found the value appeared only once then break
            if(value == 1){
                int key = (int)mapElement.getKey();
                System.out.println(key);
                break;
            }
        }
    }
}

Объяснение -
В приведенном выше коде мы сначала вычисляем частоту каждого элемента, а затем проверяем значение, которое появляется только один раз. Когда значение найдено, мы печатаем это значение и выходим из цикла, поскольку уверены, что есть только 1 элемент, который появляется ровно один раз.

6. Напишите программу для сортировки массива с помощью сортировки вставками .
Пример -
приб = [6,3,7,6,2,4,1,8,9] вывод = [1,2,3,4,6,6,7,8,9]

Решение-

import java.util.Arrays;
public class Main{
    //Insertion Sort Algorithm
    static void Sort(int A[], int n) {
        int j = 0, key = 0;
        for (int i = 1; i < n; i++) {
            //Choosing an element
            key = A[i];
            j = i - 1;
            //searching for the correct position.
            while (j >= 0 && key < A[j]) {
                A[j + 1] = A[j--];
            }
            //Inserting the element to its correct position.
            A[j + 1] = key;
        }
    }
    public static void main(String[] args) {
        int[] arr = {6,3,7,6,2,4,1,8,9};
      Sort(arr, 9);
      System.out.println(Arrays.toString(arr));
    }
}

Объяснение. Алгоритм сортировки вставками выбирает элемент из массива один за другим и пытается вставить его в соответствующую позицию. И именно этот подход мы применили в приведенном выше коде, чтобы извинить элементы в массиве.

7. Напишите программу на Java для поиска элемента в массиве, если элементы отсортированы и повернуты на несколько k шагов.
Пример -
arr = [5,6,1,2,3,4] target = 6 Вывод — элемент найден
Arr = [1,3] target = 2 Вывод — элемент не найден**

Решение -

class Main {
    private static boolean search(int[] A, int target) {
        int low = 0, high = A.length-1, mid;
        while(low <= high){
            mid = (low + high)/2;

            //Returning mid if target found on mid
            if(A[mid] == target) return true;

            //Checking if the left subarray is sorted?
            if(A[low] <= A[mid]){

                //Checking if elements exist between low to mid
                if(target >= A[low] && target <= A[mid]){

                    //if found that element exists in the range so search
                    //in the left subarray
                    high = mid-1;
                }else{

                    //if element don't exist between range the search on
                    //right sub array
                    low = mid+1;
                }            
            }else{

                // checking if target exists in the right subarray range
                if(target >= A[mid] && target <= A[high]){

                 //If element exist in range then search on right subarray
                    low = mid+1;
                }else{

                //If elements don't exist in the right subarray then search
                // on left subarray
                    high = mid-1;
                }
            }
        }
        return false; //return false if element doesn't exist in array.
    }
    public static void main(String args[]) {
        int[] arr = {6,1,2,3,4,5};
        int target = 6;

        if(search(arr, target)){
            System.out.println(" Element Found. ");
        }
        else{
            System.out.println(" Element not found in array. ");
        }
    }
}

Объяснение. В приведенном выше коде мы используем подход бинарного поиска для поиска элемента, в котором он должен присутствовать. Если элементы существуют слева от средних элементов и уже отсортированы, то мы бинарно ищем их. В противном случае мы проверяем другой размер, если он существует или нет.

8. Напишите программу на Java для вывода k-го по величине элемента массива.
Пример -
обр = [5,9,3,7,4,6,1,2,8] k = 3 Выход = 7
Объяснение. 7 — третий по величине элемент в массиве, поэтому мы можем его напечатать.

Решение -

import java.util.Arrays;
class Main {
    public static void main(String args[]) {
        int[] arr =  {5,9,3,7,4,6,1,2,8};

        //Sorting the array
        Arrays.sort(arr);
        int length = arr.length, k = 3;

        //Printing the kth element from last, as that will be the maximum.
        System.out.print(arr[length - k]);
    }
}

Объяснение -
Сначала мы сортируем элементы массива. Мы знаем, что в отсортированном массиве самый большой элемент находится в последнем индексе. Таким образом, используя это свойство, мы можем получить k-й по величине элемент, выбрав элементы из последнего, если элементы отсортированы.

9. Учитывая целочисленный массив arr и целое число k, переверните первый элемент k для каждых 2k элементов, начиная с массива. Если последние k элементов больше длины, просто пропустите их.
Пример -
обр = [2,9,3,7,5,8,3,4,2,5] k = 2 Выход = [9,2,3,7,8,5,3,4,5,2]
обр = [2,7,6,8,5,8,6,2,6,5,9,7,6,3] k = 3 Выход = [6,7,2,5,5,8,6 ,2,6,5,9,7,6,3]
Объяснение -
В выходном массиве мы видим, что элементы, выделенные жирным шрифтом, перевернуты. Потому что каждый k-й элемент нам нужно перевернуть. А во втором примере подчеркнутые элементы пропускаются, потому что они не являются полными k элементами.

Решение -

import java.util.Arrays;
class Main {
    //method to reverse the elements
    private static void reverse(int[] arr, int a, int b){
        int temp;
        while(a < b){
            temp = arr[a];
            arr[a++] = arr[b];
            arr[b--] = temp;
        }
    }
    public static void main(String args[]) {
        int[] arr = {2,7,6,8,5,8,6,2,6,5,9,7,6,3};
        int k = 3;
        int n = arr.length;

        //loop to every kth element and reverse it.
        for(int i = 0; i < n-1; i += (k*2)){
            int a = i, b = i+k-1;
            //Checking if the index exists in between the array length  
            if(b < b)
                reverse(arr, a, b);
            else
                //Break the loop if no further elements can be reversed.
                break;
        }
        System.out.println(Arrays.toString(arr));
    }
}

Объяснение -
В приведенном выше коде мы проходим через весь массив дважды по k шагов. Затем найти индекс и изменить элемент из массива. Если последний индекс k выходит за пределы, то мы завершаем цикл, а не переворачиваем массив, потому что это невозможно.

10. Напишите программу на Java, чтобы найти элемент, который встречается в массиве более n/2 раз. Если ни один элемент не встречается более n/2 раз, выведите -1.
Пример -
обр = [2,2,1,1,1,2,2] Выход = 2
обр = [2,3,3,2,5,5,7] Выход = -1
Объяснение -
В приведенном выше вводе размер массива равен = 7. И элемент, который существует больше, чем n/2 (7/2) = 3, равен 2. Поэтому нам нужно напечатать элемент 2.
Точно так же в другом примере ни один элемент не присутствует более 3 раз, поэтому мы печатаем -1.

Решение -

import java.util.*;
class Main {
    public static void main(String args[]) {
        int[] arr = {2,2,1,1,1,2,2};
        HashMap<Integer, Integer> hm = new HashMap<>();
        int n = arr.length;

        //Counting the frequency of the elements.
        for(int i : arr){
            Object val = hm.get(i);
            if(val == null)
                val = 0;
            hm.put(i, (int)val+1);
        }
        //flag to check if an element was found or not.
        boolean found = false;
        for (Map.Entry mapElement : hm.entrySet()) {
            int value = (int)mapElement.getValue();

            //Checking if such elements exist or not.
            if(value > n/2){
                int key = (int)mapElement.getKey();
                System.out.println(key);
                found = true;
                break;
            }
        }

        //Printing -1 if element is not found.
        if(!found)
            System.out.println(-1);
    }
}

Объяснение -
В приведенном выше коде мы сначала создаем частоту элемента, а затем для каждого элемента мы проверяем, что, если частота элемента больше n/2, мы печатаем и прерываем цикл, потому что мы знаем, что частота элемента post n/2 найдено, то ни один элемент больше n/2 не существует. В конце, если не найдено ни одного элемента с частотой большей, чем n/2. Затем мы печатаем -1.

References:
https://docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html
https://www.sanfoundry.com/java-programming-examples-arrays/
https://www.interviewbit.com/java-interview-questions/

Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
Card image cap
Pulsum Via

Проект для путешественников от EVILEG.

Перейти
Timeweb

Позвольте мне порекомендовать вам отличный хостинг, на котором расположен EVILEG.

В течение многих лет Timeweb доказывает свою стабильность.

Для проектов на Django рекомендую VDS хостинг

Посмотреть Хостинг
Поделиться в социальных сетях
Donate

Проект EVILEG перешёл на некоммерческую основу и будет развиваться исключительно на энтузиазме создателя сайта, энтузиазме пользователей, пожертвованиях и реферальной системе хостинга

Спасибо за вашу поддержку

Доступные способы поддержки проекта

PayPal

PatreonYooMoneyПодробнее
s

C++ - Тест 002. Константы

  • Результат:50баллов,
  • Очки рейтинга-4
s

C++ - Тест 001. Первая программа и типы данных

  • Результат:66баллов,
  • Очки рейтинга-1
r

C++ - Тест 002. Константы

  • Результат:58баллов,
  • Очки рейтинга-2
Последние комментарии

Qt/C++ - Урок 061. Добавление изображений в приложение методом Drag And Drop из файлового менеджера

Доброго времени суток. А если нужно и изображение и текст? Что-то потерялся немного.... // Вместо отрисовки иконки и текста будем отрисовывать только одно изображение // с н…
АС

Qt/C++ - Урок 004. QSqlTableModel или Как представить таблицу из БД в Qt?

error insert into TableExample " Количество параметров не совпадает" Я путь свой прописывала и даже бд удаляла, чтобы заново сделать, не работает. (всё остальное как у вас... Вроде ка…
i
ЛД

GameDev на Qt - Урок 1. Отслеживание перемещения мыши в QGraphicsScene

Вполне возможно, что ты не закинул graphicsView в дизайнере в виджет
ЛД

GameDev на Qt - Урок 1. Отслеживание перемещения мыши в QGraphicsScene

Кому интересно, поворот в slotTarget можно в одну строку организовать this->setRotation(90 + rotation() + qRadiansToDegrees(qAtan2(mapFromScene(point).y(), mapFromScene(point).x())));
Сейчас обсуждают на форуме
K

Sorting the added QML elements in the ListModel

buy accutane online forum https://isotretinoinxp.top
  • Nomad
  • 30 июля 2022 г. 5:42

Как работать с HTMX?

Приветствую колеги. На днях наткнулся на вот это : https://htmx.org/ На офф сайте написанно вот такая фраза: htmx gives you access to AJAX, CSS Transitions, We…
h
  • harisr
  • 25 июля 2022 г. 2:56

QT - Native App Integration

Привет, у нас уже есть собственное приложение для Android. Можем ли мы интегрировать пользовательское представление QT в приложение со всем приложением QT внутри представления. Если да, ука…

Правильный запуск сервера на vps - Django

О я как то себе дома локальный сервер создавал. Вам же нужно просто сделать ручками конфигурацию системы. Настроить Nginx ну либо Apache (тут кому что нравится). Соответственно БД и всё остально…
o

Распознание объектов

Я к тому, что, возможно, софт уже есть.
О нас
Услуги
© EVILEG 2015-2022
Рекомендует хостинг TIMEWEB