Масиви в 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)
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;
}
}
}
}
Пояснення -
У наведеному вище коді спочатку обчислюємо частоту кожного елемента, а потім перевіряємо значення, яке з'являється тільки один раз. Коли значення знайдено, ми друкуємо це значення і виходимо з циклу, оскільки впевнені, що є лише один елемент, який з'являється рівно один раз.
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 виходить за межі, ми завершуємо цикл, а не перевертаємо масив, тому що це неможливо.
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.
Посилання:
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/
ИМХО к каждой задаче стоит добавить решение с Stream API. К первой задаче например так:
Лаконичней ведь :)