sonia jessica
21 червня 2022 р. 13:34

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

Зміст
  1. 1. Масиви в java:
  2. 2. Java-програми для роботи з масивами

Масиви в java:

  • Масив - це базова структура даних, що містить елементи подібних типів даних.
    – Завжди є порядок серед позицій елемента.
    – Доступ до нього можна отримати за допомогою індексів. Java підтримує масиви з нульовим індексом. Означає, що індекс масиву починається з 0 в java.
  • Ми можемо оголосити масив у java як-
    1.int[] arr = новий int[розмір];
    2.int[] arr = {1,2,3…};
    3.int[] arr = новий 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. }

Пояснення -
У наведеному вище коді спочатку обчислюємо частоту кожного елемента, а потім перевіряємо значення, яке з'являється тільки один раз. Коли значення знайдено, ми друкуємо це значення і виходимо з циклу, оскільки впевнені, що є лише один елемент, який з'являється рівно один раз.

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 виходить за межі, ми завершуємо цикл, а не перевертаємо масив, тому що це неможливо.

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.

Посилання:
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
  • 09 серпня 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

Коментарі

Only authorized users can post comments.
Please, Log in or Sign up
Actions
Напишіть статтюЗадайте питанняЗробіть тестПоділитися кодом