Zusammenfassung häufiger Array-Fragen in Java-Interviews (1)

Schwierigkeitsgrad der Frage: * *

(Lernvideo-Empfehlung: Java-Kurs)

1. Sortierreihenfolge

[Titel]

Gibt den sortierten Wert eines numerischen Arrays zurück, z. B. Daten [6,2 ,5 ,0] gibt [4,2,3,1]

[Code]

package swear2offer.array;

import java.util.Arrays;

public class SortSequence {
    /**
     * 返回一个数字数组的排序值
     * 比如数据 [6,2,5,0] 的返回是 [4,2,3,1]
     * */
    public int[] compare(int[] a) {
        int i,j,n;
        n = a.length;

        int [] c = new int[n];

		//数组下标从0开始，但是输出的次序从1开始，所以需要初始化数组为1
        for (i=0; i<n; i++) {
           c[i]++;
        }

        for (i=0; i<n; i++) {
            for (j=0; j<i; j++) {
                if (a[j]<a[i]) c[i]++;
                else c[j]++;
            }
        }

        return c;
    }

    public static void main(String[] args) {
        int[] a = {6,2,5,0};
        System.out.println(Arrays.toString(new SortSequence().compare(a)));
    }

}

[Denken]

Der normale Weg, die Reihenfolge zu erhalten, besteht darin, jedes Element mit allen anderen Elementen zu vergleichen und dann die Größe zu ermitteln order , aber hier wird die trapezförmige Vergleichsreihenfolge verwendet.

2. Array-Index-Hilfsdatensatz

[Titel]

Gegebenes Array a mit einer Länge von N und einem Elementwertbereich von [1, N], zählen Sie die Anzahl der Vorkommen jedes Elements und die erforderliche Zeitkomplexität ist O (N), die Raumkomplexität ist O (1)

[Code]

6
6 2
6 2 5
6 2 5 0

(Empfohlenes grafisches Tutorial:

Java-Interviewfragen und -antworten

)3. Finden Sie die Elemente eines geordneten zweidimensionalen Arrays

[Titel 】

In einem zweidimensionalen Array (jedes eindimensionale Array hat die gleiche Länge) wird jede Zeile in aufsteigender Reihenfolge von links nach rechts und jede Spalte in aufsteigender Reihenfolge von oben nach unten sortiert. Bitte vervollständigen Sie eine Funktion, geben Sie ein solches zweidimensionales Array und eine Ganzzahl ein und bestimmen Sie, ob das Array die Ganzzahl enthält.

[Code]

/**
     * 这类要求空间O(1)时间复杂度为O(n)的问题
     * 需要在一次遍历并且不声明新数组的情况下求解，这种题目通常要求元素大小跟下标大小一致。
     * 所以通常考虑是利用数组存储的元素和数组下标来求解
     * 在本题中，数组的元素变成了下标，而数组内元素则表示之前元素出现的次数，0则代表不出现。
     * 为了区分元素和次数，可以把次数设定为负值
     * */
    public void Solution(int[] a) {
        int i,n,temp;
        n = a.length;

        i = 0;
        /**
         * 只有在temp小于0的时候才会推进循环
         * */
        while(i < n) {
            temp = a[i]-1;
            // 如果数组元素小于0，则代表该数已经被替换到其他地方或者已经被计数过从而被覆盖
            if (temp < 0) {
                i ++;
                continue;
            }
            // 把未记录的数保存在已经记录的位置上，并用负值保存数量
            if (a[temp]>0) {
                a[i] = a[temp];
                a[temp] = -1;
            } else {
                a[i] = 0; //该数据已经使用过，且表示元素i+1出现0次
                a[temp]--;
            }
        }

    }

[Denken]

Ausgehend von oben links gibt es zu viele Situationen, die berücksichtigt werden müssen, da sowohl nach rechts als auch nach unten zunimmt, aber von oben rechts aus nach links abnehmend und nach unten zunehmend, so dass die Situation auf eins beschränkt ist. Spezielle Arrays, nutzen Sie die Besonderheiten von Arrays voll aus und berücksichtigen Sie Methoden aus verschiedenen Richtungen.

4. Stufen hochspringen

[Thema]

Ein Frosch kann 1 Stufe oder 2 Stufen gleichzeitig hochspringen. Finden Sie heraus, auf wie viele Arten der Frosch eine n-stufige Stufe hochspringen kann (unterschiedliche Ergebnisse werden in unterschiedlicher Reihenfolge berechnet). 5. Abnormale Sprungtreppen Finden Sie die Gesamtzahl der Möglichkeiten, auf denen der Frosch eine Treppe mit n Ebenen hinaufspringen kann.

【Code】

package swear2offer.array;

public class ArrayFind {

    /**
     * 在一个二维数组中（每个一维数组的长度相同），
     * 每一行都按照从左到右递增的顺序排序，
     * 每一列都按照从上到下递增的顺序排序。
     * 请完成一个函数，输入这样的一个二维数组和一个整数，
     * 判断数组中是否含有该整数。
     *
     * 思路：
     * 从左上出发，需要考虑的情况太多，因为向右和向下都是递增
     * 但是从右上出发，向左递减，向下递增，这样就把情况限定在一种。
     * */
    public boolean Find(int target, int [][] array) {

        int l,h,x,y;
        h = array.length;
        l = array[0].length;

        // 游标的横纵坐标
        x = l-1;
        y = 0;

        while (x>=0 && y<h) {
            if(array[y][x] == target) {
                return true;
            }

            if (array[y][x]<target) {
                y++;
            } else {
                x--;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        int[][] a = {{1,3,5,6},{2,4,7,8},{5,8,9,12}};
        System.out.println(new ArrayFind().Find(11,a));
    }

}

Verwandte Empfehlungen:

Erste Schritte mit Java

Das obige ist der detaillierte Inhalt vonZusammenfassung häufiger Array-Fragen in Java-Interviews (1). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!