sonia jessica
21 июня 2022 г. 13:34

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

Содержание
  1. 1. Массивы в java:
  2. 2. 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) 

  1. import java.util.Arrays;
  2. class Main {
  3.     public static void main(String args[]) {
  4.         int[] arr = {4, 9, 6, 8};
  5.         int[] output = new int[arr.length];
  6.         for(int i = 0; i < arr.length; i++){
  7.             int mul = 1;
  8.             //Loop for multiplying the values of the array.
  9.             for(int j = 0; j < arr.length; j++){
  10.                 //Skipping the element for the current index 
  11.                 if(i == j)
  12.                     continue;
  13.                 mul *= arr[j];
  14.             }
  15.             //Assigning the values to the current index
  16.             output[i] = mul;
  17.         }
  18.         //Printing the output array.
  19.         System.out.print(Arrays.toString(output));
  20.     }
  21. }

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

Подход 2 (Optimized) 

  1. import java.util.Arrays;
  2. class Main {
  3.     public static void main(String args[]) {
  4.         int[] arr = {9,6,7,8};
  5.         int[] output = new int[arr.length];
  6.         int multiply = 1;
  7.  
  8.         //Calculating the multiplication of all the elements.
  9.         for(int n : arr)
  10.             multiply *= n;
  11.  
  12.         //Assigning to the output array after diving with the
  13.         //elements from input array.
  14.         for(int i = 0; i < arr.length; i++)
  15.             output[i] = multiply / arr[i];
  16.  
  17.         //Printing the output array.
  18.         System.out.println(Arrays.toString(output));
  19.     }
  20. }

В этом подходе мы сначала вычисляем умножение всех элементов, а затем присваиваем значения выходной переменной путем деления ее на текущий индексированный элемент. Так мы избегаем повторения работы. И нам нужно всего 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) 

  1. import java.util.Arrays;
  2. class Main {
  3.     public static void main(String args[]) {
  4.         int[] arr =  {8, 0, 0, 7, 3, 0, 2};
  5.         int[] output = new int[arr.length];
  6.  
  7.         //Pointer for adding the value in the output array.
  8.         int k = 0;
  9.         for(int i = 0; i < arr.length; i++){
  10.             //Skipping the element if it is 0.
  11.             if(arr[i] == 0)
  12.                 continue;
  13.  
  14.             //Assigning the next value to the output variable.
  15.             output[k] = arr[i];
  16.             k++;
  17.         }
  18.         //Printing the output.
  19.         System.out.print(Arrays.toString(output));
  20.     }
  21. }

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

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

  1. import java.util.Arrays;
  2. class Main {
  3.     public static void main(String args[]) {
  4.         int[] arr =  {8, 0, 0, 7, 3, 0, 2};
  5.         int i = 0, j = 0;
  6.  
  7.         while(i < arr.length){
  8.             //if find 0 then continue until nonzero found.
  9.             if(arr[i] == 0){
  10.                 i++;
  11.             }else{
  12.                 //Swapping the values of 1st non-zero number found after 0
  13.                 int temp = arr[j];
  14.                 arr[j] = arr[i];
  15.                 arr[i] = temp;
  16.                 i++;
  17.                 j++;
  18.             }
  19.         }
  20.         //Printing the output.
  21.         System.out.print(Arrays.toString(arr));
  22.     }
  23. }

В приведенном выше коде мы взяли 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) 

  1. import java.util.ArrayList;
  2. class Main {
  3.     public static void main(String args[]) {
  4.         int[] arr = {8, 2, 5, 7, 3, 4, 2};
  5.         //Creating ArrayList that will contain the leader elements.
  6.         ArrayList<Integer> ans = new ArrayList<>();
  7.  
  8.         for(int i = 0; i < arr.length; i++){
  9.             boolean flag = true;
  10.  
  11.             //Checking if the particular element is the leader.
  12.             for(int j = i+1; j < arr.length; j++){
  13.  
  14.                 //If it's not the leader then changing the flag to false 
  15.                 //and break
  16.                 if(arr[j] > arr[i]){
  17.                     flag = false;
  18.                     break;
  19.                 }
  20.             }
  21.             //if flag is not false then we know that the element is the 
  22.             //leader adds in the answer.
  23.             if(flag)
  24.                 ans.add(arr[i]);
  25.         }
  26.         //Printing the answer.
  27.         System.out.println(ans);
  28.     }
  29. }

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

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

  1. import java.util.ArrayList;
  2. class Main {
  3.     public static void main(String args[]) {
  4.         int[] arr = {8, 2, 5, 7, 3, 4, 2};
  5.  
  6.         //Declaring Result array to store the leader element
  7.         ArrayList<Integer> ans = new ArrayList<>();
  8.  
  9.         //n represents the length of array size and max will 
  10.         //store the last element of the array.
  11.         int n = arr.length, max = arr[n-1];
  12.         ans.add(max);
  13.         for(int i = n-2; i >= 0; i--){
  14.             //If found another leader then changing the leader
  15.             //and add to the answer array.
  16.             if(arr[i] > max){
  17.                 ans.add(arr[i]);
  18.                 max = arr[i];
  19.             }
  20.         }
  21.         //Printing the leader array.
  22.         System.out.print(ans);
  23.     }
  24. }

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

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

Решение - 

  1. class Main {
  2.     private static int findPeak(int[] arr, int low, int high){
  3.         if(high == low) // Corner case when only a single element is present.
  4.         return low;
  5.         while(low < high){
  6.             //calculating the mid index                                     
  7.             int mid = (low + high) / 2;
  8.  
  9.             //checking if the element of mid+1 is the peak
  10.             if (mid < high && arr[mid] > arr[mid + 1])
  11.                 return mid;
  12.  
  13.             //checking if the element of mid-1 is the peak
  14.             else if (mid > low && arr[mid] < arr[mid - 1])
  15.                 return (mid - 1);
  16.  
  17.             //checking if element exists on the left side of array from mid then 
  18.             //search on left side
  19.             else if (arr[low] >= arr[mid])
  20.                 high = mid - 1;
  21.  
  22.             //checking if element exists on right side of array from mid 
  23.             //then search on right
  24.             else 
  25.                 low = mid + 1;
  26.         }
  27.         return -1; // returning -1 if element is completely sorted
  28.     }
  29.     public static void main(String args[]) {
  30.         int[] arr = {4, 5, 7, 1, 2, 3};
  31.         int peak = findPeak(arr, 0, arr.length-1);
  32.         System.out.print(peak);
  33.     }
  34. }

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

Решение - 

  1. import java.util.*;
  2. class Main {
  3.     public static void main(String args[]) {
  4.         HashMap<Integer, Integer> hm = new HashMap<>();
  5.         int[] arr = {2,6,8,5,6,7,1,2,5,6,1,1,9,8,9};
  6.  
  7.         //loop to count the frequency of the element in the array.
  8.         for(int i : arr){
  9.             Object val = hm.get(i);
  10.             if(val == null)
  11.                 val = 0;
  12.  
  13.             //If an element exists then increasing its frequency.
  14.             hm.put(i, (int)val+1);
  15.         }
  16.         for (Map.Entry mapElement : hm.entrySet()) {
  17.             int value = (int)mapElement.getValue();
  18.             //If found the value appeared only once then break
  19.             if(value == 1){
  20.                 int key = (int)mapElement.getKey();
  21.                 System.out.println(key);
  22.                 break;
  23.             }
  24.         }
  25.     }
  26. }

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

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

Решение- 

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

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

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

Решение - 

  1. class Main {
  2.     private static boolean search(int[] A, int target) {
  3.         int low = 0, high = A.length-1, mid;
  4.         while(low <= high){
  5.             mid = (low + high)/2;
  6.  
  7.             //Returning mid if target found on mid
  8.             if(A[mid] == target) return true;
  9.  
  10.             //Checking if the left subarray is sorted?
  11.             if(A[low] <= A[mid]){
  12.  
  13.                 //Checking if elements exist between low to mid
  14.                 if(target >= A[low] && target <= A[mid]){
  15.  
  16.                     //if found that element exists in the range so search
  17.                     //in the left subarray
  18.                     high = mid-1;
  19.                 }else{
  20.  
  21.                     //if element don't exist between range the search on
  22.                     //right sub array
  23.                     low = mid+1;
  24.                 }            
  25.             }else{
  26.  
  27.                 // checking if target exists in the right subarray range
  28.                 if(target >= A[mid] && target <= A[high]){
  29.  
  30.                  //If element exist in range then search on right subarray
  31.                     low = mid+1;
  32.                 }else{
  33.  
  34.                 //If elements don't exist in the right subarray then search
  35.                 // on left subarray
  36.                     high = mid-1;
  37.                 }
  38.             }
  39.         }
  40.         return false; //return false if element doesn't exist in array.
  41.     }
  42.     public static void main(String args[]) {
  43.         int[] arr = {6,1,2,3,4,5};
  44.         int target = 6;
  45.  
  46.         if(search(arr, target)){
  47.             System.out.println(" Element Found. ");
  48.         }
  49.         else{
  50.             System.out.println(" Element not found in array. ");
  51.         }
  52.     }
  53. }

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

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

Решение - 

  1. import java.util.Arrays;
  2. class Main {
  3.     public static void main(String args[]) {
  4.         int[] arr =  {5,9,3,7,4,6,1,2,8};
  5.  
  6.         //Sorting the array
  7.         Arrays.sort(arr);
  8.         int length = arr.length, k = 3;
  9.  
  10.         //Printing the kth element from last, as that will be the maximum.
  11.         System.out.print(arr[length - k]);
  12.     }
  13. }

Объяснение -
Сначала мы сортируем элементы массива. Мы знаем, что в отсортированном массиве самый большой элемент находится в последнем индексе. Таким образом, используя это свойство, мы можем получить 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 элементами.

Решение - 

  1. import java.util.Arrays;
  2. class Main {
  3.     //method to reverse the elements
  4.     private static void reverse(int[] arr, int a, int b){
  5.         int temp;
  6.         while(a < b){
  7.             temp = arr[a];
  8.             arr[a++] = arr[b];
  9.             arr[b--] = temp;
  10.         }
  11.     }
  12.     public static void main(String args[]) {
  13.         int[] arr = {2,7,6,8,5,8,6,2,6,5,9,7,6,3};
  14.         int k = 3;
  15.         int n = arr.length;
  16.  
  17.         //loop to every kth element and reverse it.
  18.         for(int i = 0; i < n-1; i += (k*2)){
  19.             int a = i, b = i+k-1;
  20.             //Checking if the index exists in between the array length  
  21.             if(b < b)
  22.                 reverse(arr, a, b);
  23.             else
  24.                 //Break the loop if no further elements can be reversed.
  25.                 break;
  26.         }
  27.         System.out.println(Arrays.toString(arr));
  28.     }
  29. }

Объяснение -
В приведенном выше коде мы проходим через весь массив дважды по 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.

Решение - 

  1. import java.util.*;
  2. class Main {
  3.     public static void main(String args[]) {
  4.         int[] arr = {2,2,1,1,1,2,2};
  5.         HashMap<Integer, Integer> hm = new HashMap<>();
  6.         int n = arr.length;
  7.  
  8.         //Counting the frequency of the elements.
  9.         for(int i : arr){
  10.             Object val = hm.get(i);
  11.             if(val == null)
  12.                 val = 0;
  13.             hm.put(i, (int)val+1);
  14.         }
  15.         //flag to check if an element was found or not.
  16.         boolean found = false;
  17.         for (Map.Entry mapElement : hm.entrySet()) {
  18.             int value = (int)mapElement.getValue();
  19.  
  20.             //Checking if such elements exist or not.
  21.             if(value > n/2){
  22.                 int key = (int)mapElement.getKey();
  23.                 System.out.println(key);
  24.                 found = true;
  25.                 break;
  26.             }
  27.         }
  28.  
  29.         //Printing -1 if element is not found.
  30.         if(!found)
  31.             System.out.println(-1);
  32.     }
  33. }

Объяснение -
В приведенном выше коде мы сначала создаем частоту элемента, а затем для каждого элемента мы проверяем, что, если частота элемента больше 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 хостинг.

По статье задано0вопрос(ов)

1
18

Вам это нравится? Поделитесь в социальных сетях!

2.9K
1
1
4
0
Vladimir Sergeevich
  • 9 августа 2023 г. 14:19

ИМХО к каждой задаче стоит добавить решение с Stream API. К первой задаче например так: 

  1. import java.util.Arrays;
  2. class Main {
  3.     public static void main(String args[]) {
  4.         int[] arr = {9,6,7,8};
  5.  
  6.         int multiply = Arrays.stream(arr)
  7.             .reduce((left, right) -> (left * right))
  8.             .getAsInt();
  9.  
  10.         int[] output = Arrays.stream(arr)
  11.                       .map(value -> multiply/value)
  12.                       .toArray();
  13.  
  14.         Arrays.stream(output).forEach(System.out::println);
  15.     }
  16. }

Лаконичней ведь :)

0
1
0

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
Actions
Написать статьюЗадать вопросПройти тестРасшарить код