Arrays in Java:
- Ein Array ist eine grundlegende Datenstruktur, die Elemente ähnlicher Datentypen enthält.
- Es gibt immer eine Reihenfolge zwischen den Positionen eines Elements.
- Es kann über Indizes zugegriffen werden. Java unterstützt Arrays mit Index Null. Bedeutet, dass der Array-Index in Java bei 0 beginnt.
-
Wir können ein Array in Java deklarieren wie -
1.int[] arr = new int[Größe];
2.int[] arr = {1,2,3…};
3.int[] arr = new int[]{1,2,3,...};
In diesem Artikel werfen wir einen Blick auf einige Java-Array-Interviewprogramme, die am häufigsten in Java-Interviews gefragt werden.
Java-Programme zum Arbeiten mit Arrays
eines. Gegeben sei ein Array arr der Größe n. Ihre Aufgabe besteht darin, ein Ausgabearray basierend auf dem Eingabearray zu erstellen, und die Elemente sind das Produkt aller Elemente des Eingabearrays, mit Ausnahme des Werts am aktuellen Index.
Beispiel -
arr = [4, 9, 6, 8] ausgabe = [432, 192, 288, 216]
Erläuterung -
Bei Index 0 ist die Multiplikation aller Elemente außer 4 - (9 * 6 * 8) = 432.
Bei Index 1 ist die Multiplikation aller Elemente außer 9 - (4 * 6 * 8) = 192.
Bei Index 2 ist die Multiplikation aller Elemente außer 6 - (4 * 9 * 8) = 288.
Bei Index 3 ist die Multiplikation aller Elemente außer 8 - (4 * 9 * 6) = 216.
Antworten -
Ansatz 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));
}
}
Bei diesem Ansatz weisen wir dem Ausgabearray Werte für den aktuellen Index zu. Und jedes Mal berechnen wir den Wert, der einem bestimmten Index zuzuordnen ist. Dieser Ansatz benötigt O(n^2) Zeit. Denn für jeden Index berechnen wir das Ergebnis.
Ansatz 2 (optimiert)
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));
}
}
Bei diesem Ansatz berechnen wir zunächst die Multiplikation aller Elemente und weisen dann der Ausgangsvariablen Werte zu, indem wir sie durch das aktuell indizierte Element dividieren. So vermeiden wir Wiederholungsarbeiten. Und wir brauchen nur 2 separate Iterationen der Schleife. Die Zeitkomplexität wird also O(n) sein.
2. Schreiben Sie ein Java-Programm, um alle Nullen an das Ende eines Arrays zu verschieben.
Beispiel -
Ink = [8, 0, 0, 7, 3, 0, 2] Ausgabe = [8, 7, 3, 2, 0, 0, 0]
Erläuterung -
An Index 1 befindet sich eine 0. Die 0 wird also an die letzte verschoben und das erste Nicht-Null-Element wird an den 1. Index verschoben.
Ebenso für Index 2 und 5 auch.
Antworten -
Ansatz (mit Hilfsarray)
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));
}
}
Im obigen Ansatz erstellen wir ein zusätzliches Array und fügen ihm einen Wert ungleich Null hinzu, sodass der verbleibende Platz im Array mit 0 gefüllt wird. Die Zeitkomplexität dieses Ansatzes ist O(n) und die Raumkomplexität ist ebenfalls O .(n).
Ansatz 2 (mit 2 Zeigern) -
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));
}
}
Im obigen Code haben wir 2 Zeiger genommen. Einer zeigt auf die nächste 0, die zuletzt gesendet werden soll, und der andere ist das nächste Element, das den Index des ersten Zeigers ersetzt. Die Zeitkomplexität davon ist O(n) und die Raumkomplexität ist konstant O(1).
3. Schreiben Sie ein Java-Programm, um ein Array auszugeben, das Leader aus einem gegebenen Eingabe-Array enthält. Der Anführer ist das Element, dessen alle Elemente rechts kleiner sind als es.
Beispiel -
Ink = [8, 2, 5, 7, 3, 4, 2] Ausgabe = [2, 4, 7, 8]
Erläuterung -
Wir sehen, dass 2 der Leader ist, weil 2 das letzte Element im Array ist. 4 ist auch der Anführer, weil nach 4 alle Elemente kleiner sind. Und auch 7 und 8 auch.
Antworten -
Ansatz 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);
}
}
Beim obigen Ansatz prüfen wir jedes Element, ob es sich um einen Anführer handelt oder nicht. Somit beträgt die Zeitkomplexität für den oben beschriebenen Ansatz O(n2).
Ansatz 2 (optimiert)-
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);
}
}
Bei diesem Ansatz prüfen wir den Anführer des Elements und finden den größten. Weil es der Anführer sein wird, da sich alle kleineren Elemente auf der rechten Seite befinden. Die Zeitkomplexität für diesen Ansatz ist also O(n).
vier. Schreiben Sie ein Java-Programm, um den Index des Peak-Elements in einem Array zu finden. Das Spitzenelement ist größer als seine linken und rechten Elemente.
Beispiel -
arr = [4, 5, 7, 1, 2, 3] Ausgabe = 2
Erläuterung -
Wir sehen, dass das Element bei Index 2 = (7) größer als links und rechts ist. Element (5 und 1).
Antworten -
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. Gegeben sei ein Array aus n Elementen, in dem jedes Element bis auf ein Element mindestens zweimal vorkommt. Schreiben Sie also ein Java-Programm, um dieses Element zu finden.
Beispiel -
arr=[2,6,8,5,6,7,1,2,5,6,1,1,9,8,9] ausgabe=7
Erläuterung -
Im obigen Array ist nur 7 ein Element, das nur einmal vorkommt, also geben Sie dieses Element aus.
Antworten -
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;
}
}
}
}
Erläuterung -
Im obigen Code berechnen wir zuerst die Häufigkeit jedes Elements und suchen dann nach einem Wert, der nur einmal vorkommt. Wenn ein Wert gefunden wird, geben wir diesen Wert aus und verlassen die Schleife, weil wir sicher sind, dass nur 1 Element genau einmal vorkommt.
6. Schreiben Sie ein Programm, um ein Array mit Insertion Sort
zu sortieren.
Beispiel -
Ink = [6,3,7,6,2,4,1,8,9] Ausgang = [1,2,3,4,6,6,7,8,9]
Antworten-
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));
}
}
Erläuterung. Der Insertion-Sort-Algorithmus wählt ein Element nach dem anderen aus dem Array aus und versucht, es an der richtigen Position einzufügen. Und das ist genau der Ansatz, den wir im obigen Code gewählt haben, um die Elemente im Array zu entschuldigen.
7. Schreiben Sie ein Java-Programm, um ein Element in einem Array zu finden, wenn die Elemente sortiert und um k Schritte rotiert werden.
Beispiel -
arr = [5,6,1,2,3,4] target = 6 Ausgabe - Element gefunden
Arr = [1,3] Ziel = 2 Ausgabe - Element nicht gefunden**
Antworten -
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. ");
}
}
}
Erläuterung. Im obigen Code verwenden wir einen binären Suchansatz, um das Element zu finden, wo es vorhanden sein sollte. Wenn Elemente links von den mittleren Elementen existieren und bereits sortiert sind, dann suchen wir binär nach ihnen. Andernfalls prüfen wir, ob eine andere Größe vorhanden ist oder nicht.
acht. Schreiben Sie ein Java-Programm, um das k-größte Element eines Arrays auszugeben.
Beispiel -
arr = [5,9,3,7,4,6,1,2,8] k = 3 Ausgabe = 7
Erläuterung. 7 ist das drittgrößte Element im Array, also können wir es drucken.
Antworten -
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]);
}
}
Erläuterung -
Zuerst sortieren wir die Elemente des Arrays. Wir wissen, dass sich in einem sortierten Array das größte Element am letzten Index befindet. Mit dieser Eigenschaft können wir also das k-größte Element erhalten, indem wir die Elemente vom letzten auswählen, wenn die Elemente sortiert sind.
9. Bei einem ganzzahligen Array arr und einer ganzen Zahl k wird das erste Element k für alle 2k Elemente, beginnend mit dem Array, umgedreht. Wenn die letzten k Elemente größer als die Länge sind, überspringe sie einfach.
Beispiel -
arr = [2,9,3,7,5,8,3,4,2,5] k = 2 Ausgabe = [9,2,3,7,8,5,3,4,5,2]
arr = [2,7,6,8,5,8,6,2,6,5,9,7,6,3] k = 3 Ausgabe = [6,7,2,5,5,8,6 ,2,6,5,9,7,6,3]
Erläuterung -
Im Ausgabearray können wir sehen, dass die fett gedruckten Elemente umgekehrt sind. Weil wir jedes k-te Element umdrehen müssen. Und im zweiten Beispiel werden die unterstrichenen Elemente übersprungen, weil sie keine vollen k Elemente sind.
Antworten -
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));
}
}
Erläuterung -
Im obigen Code durchlaufen wir das gesamte Array zweimal in k Schritten. Suchen Sie dann den Index und ändern Sie das Element aus dem Array. Wenn der letzte Index k außerhalb der Grenzen liegt, beenden wir die Schleife, anstatt das Array umzudrehen, da dies nicht möglich ist.
zehn. Schreiben Sie ein Java-Programm, um ein Element zu finden, das mehr als n/2 Mal in einem Array vorkommt. Wenn kein Element mehr als n/2 Mal vorkommt, drucke -1.
Beispiel -
arr=[2,2,1,1,1,2,2] ausgabe=2
arr=[2,3,3,2,5,5,7] ausgabe=-1
Erläuterung -
In der obigen Eingabe ist die Größe des Arrays = 7. Und das Element, das mehr als n/2(7/2) = 3 existiert, ist 2. Also müssen wir Element 2 drucken.
In ähnlicher Weise ist im anderen Beispiel kein Element mehr als dreimal vorhanden, also geben wir -1 aus.
Antworten -
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);
}
}
Erläuterung -
Im obigen Code erstellen wir zuerst die Elementfrequenz und prüfen dann für jedes Element, dass wir drucken und die Schleife unterbrechen, wenn die Elementfrequenz größer als n/2 ist, da wir wissen, dass die Elementfrequenz nach n/2 gefunden wird, dann kein Element größer als n/2 existiert nicht. Am Ende, wenn kein Element mit einer Häufigkeit größer als n/2 gefunden wird. Wir drucken dann -1.
Verweise:
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. К первой задаче например так:
Лаконичней ведь :)