Meituan インタビュー: 簡単なスケジュールを手書きしてください。ショックを受けました。-＆＃＆面接の質問-php.cn

Meituan インタビュー: 簡単なスケジュールを手書きしてください。ショックを受けました。

リリース： 2023-08-24 15:20:01

転載

1197 人が閲覧しました

今日は、この質問を面接官がその場で手書きで手早く整理してもらいました。 : チャットを続けましょう。データ構造とアルゴリズムについて、簡単なソートを書いてもらえますか? （話している間、彼は私の履歴書をひっくり返してペンを渡しました。つまり、履歴書の裏に書くように言われました）

新人の私: どういう意味ですか?ここに書きますか？（履歴書を指しながら）

面接官: はい

新人の私: いいえ

面接官: はい、今日の面接はこれで終わりです

新人の私: (とても怒っています。これは労使の履歴書です。労使の履歴書にコードを書きますか?) Shadiao

インタビュアー: (振り返り、混乱して)

よく考えたらまだ若かったけど、今はそんなことはないでしょう。とにかく書くだけ、それはただの紙切れです。

実は、クイックキューは簡単なのですが、手書きで書けない人も多いのではないでしょうか?難しいですか? いくつかの方法でその場で手書きできる人もたくさんいます。

Meituan インタビュー: 簡単なスケジュールを手書きしてください。ショックを受けました。私は初心者ですが手書きはできるので、面接前に意図的に「

口述筆記

」を準備しただけです。

次に分析分析----クイックソートを行っていきます。

背景

百科事典より:

クイックソートは、1962 年に C. A. R. Hoare によって提案されました。その基本的な考え方は、1 回の並べ替えで並べ替え対象のデータを 2 つの独立した部分に分割することです。一方の部分のすべてのデータは、もう一方の部分のすべてのデータよりも小さいため、この方法を使用して、データの 2 つの部分をすばやく分離します。並べ替えでは、並べ替えプロセス全体を [再帰的に ] 実行できるため、データ全体が順序付けされたシーケンスになります。

この概念を理解するのは非常に困難です。

これは次のように理解できます:

クイックソートはバブルソートの改良版です。全体のプロセスは、物事をばらばらにしてつなぎ合わせることです。すべての要素は順序付けられた状態に達します。

中心的なアイデア:

まずシーケンスから基本番号として数値を取得し、次にサイズ分割を実行します;

分割プロセス中に、この数値を比較します。大きい数値をすべて右側に配置し、それ以下の数値をすべて左側に配置します。

各間隔に数値が 1 つだけになるまで、左右の間隔に対して 2 番目のステップを繰り返します。 , これで並び替えは完了です。

導入事例

以下は、写真の形式で段階的に分解したものです。そしてテキスト。

配列 [4,1,6,2,9,3] を例として取り上げます。

最初のパス:

先進行拆分[4,1,6,2,9,3] 選擇元素4 為軸心點
檢查是否1 < 4 (軸心點)
檢查是否6 < 4 (軸心點)
檢查是否2 < 4 (軸心點)
2 < 4 (軸心點) 是為真，將指數2和儲存指數6 進行交換
##檢查是否9 < 4 (軸心點)
檢查是否3 < 4 (軸心點)
3 < 4 (軸心點) 為真，將指數3和儲存指數6 進行交換
將軸心點4和儲存指數3進行交換
此時軸心點4左邊全部小於4，右邊大於4

Meituan インタビュー: 簡単なスケジュールを手書きしてください。ショックを受けました。

#目前陣列順序為[3，1，2，4，9， 6]。

下一步：

先將左邊先排好序
選擇元素3 為軸心點
檢查是否1 < 3 (軸心點)
#檢查是否2 < 3 (軸心點)
將軸心點3和儲存指數值2進行交換
現在軸心點已經在排序後的位置
#進行分割[2,1] 選擇2 為軸心點
檢查是否1 < 2 (軸心點)
左邊遍歷完成，將軸心點2和儲存指數1 進行交換

右邊同理…避免視覺疲勞就不一一描述了，可看下面動態示範圖。

Meituan インタビュー: 簡単なスケジュールを手書きしてください。ショックを受けました。

2. 快速排序法全流程

Meituan インタビュー: 簡単なスケジュールを手書きしてください。ショックを受けました。

3.程式碼實作

下面，我們使用Java語言來實作前面的快排案例：

import java.util.Arrays;

public class QuickSortDemo {
    //四个步骤：
    //1.比较startIndex和endIndex，更喜欢理解为校验
    //2.找出基准
    //3.左边部分排序
    //4.右边排序
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            //找出基准
            int partition = partition(arr, startIndex, endIndex);
            //分成两边递归进行
            quickSort(arr, startIndex, partition - 1);
            quickSort(arr, partition + 1, endIndex);
        }
    }

    //找基准
    private static int partition(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        
        int left = startIndex;
        int right = endIndex;
        
        //等于就没有必要排序
        while (left != right) {
            
            while (left < right && arr[right] > pivot) {
                right--;
            }
          
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //找到left比基准大，right比基准小，进行交换
            if (left < right) {
                swap(arr, left, right);
            }
        }
        //第一轮完成，让left和right重合的位置和基准交换，返回基准的位置
        swap(arr, startIndex, left);
        return left;
    }

    //两数交换
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] a = {3, 1, 2, 4, 9, 6};
        quickSort(a, 0, a.length - 1);
        //输出结果
        System.out.println(Arrays.toString(a));
    }
}

ログイン後にコピー

輸出結果：