Массивы в 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/
ИМХО к каждой задаче стоит добавить решение с Stream API. К первой задаче например так:
Лаконичней ведь :)