LeetCode | 實現排序比較函數 | Relative Sort Array

2021-03-02 PapaMelon 算法研究所

https://leetcode.com/problems/relative-sort-array/

題意

給出一個 arr2 數組，裡面每個 int 不會有重複；給出另一個 arr1 數組，要對 arr1 數組排序，使其滿足以下規則：


class Solution {public:    int vis[1010];    vector<int> relativeSortArray(        vector<int>& arr1, vector<int>& arr2) {      memset(vis, -1, sizeof vis);      for (int i = 0; i < arr2.size(); ++i) vis[arr2[i]] = i;
      auto cmp = [this](const int x, const int y) {        if (vis[x] == -1 && vis[y] == -1) {          return x < y;        }
        if (vis[x] == -1) return false;        if (vis[y] == -1) return true;
        return vis[x] < vis[y];      };
      sort(arr1.begin(), arr1.end(), cmp);
      return arr1;    }};
本題很多做法，我們說一個實現和理解起來都比較容易的。
實現排序的 compare 函數
注意到一點，arr2 裡面的元素都不會有重複，因此我們可以記錄下每個元素所處的位置，例如 arr2 = {2,1,4,3,9,6}，可以得到如下位置記錄
  pos[2] = 0
  pos[1] = 1
  pos[4] = 2
  pos[3] = 3
  pos[9] = 4
  pos[6] = 5
當我們對 arr1 進行排序的時候，需要對比 a，b 兩個數字，使用以下規則：
若 a，b 兩個數字都在 arr2 中出現過，則查看 pos 數組，對比 pos[a] 和 pos[b]，從而知道 a，b 哪個排前面
  若 a，b 只有一個出現在 arr2，則出現過的排前面，沒出現過的排後面
  若 a，b 都不在 arr2 中出現過，則直接比較它們的值，決定誰排在前面
PapaMelon, 讓算法好玩
關注 B 站 不愛睡覺的大豬
獲取更好的視頻體驗

相關焦點

  • [LeetCode] 912. Sort an Array 數組排序
    ，在平時刷其他題的時候，遇到要排序的時候，一般都會調用系統自帶的排序函數，像 C++ 中直接就調用 sort 函數即可，但是這道題考察的就是排序，再調用系統的排序函數就有些說不過去了。這裡需要自己實現排序功能，常見排序方法有很多，插入排序，選擇排序，堆排序，快速排序，冒泡排序，歸併排序，桶排序等等。它們的時間複雜度不盡相同，這道題貌似對於平方級複雜度的排序方法會超時，所以只能使用那些速度比較快的排序方法啦。
  • JavaScript函數補完:sort()排序
    sort() 方法用於對數組的元素進行排序。語法如下：arrayObject.sort(sortby)返回值為對數組的引用。請注意，數組在原數組上進行排序，不生成副本。如果調用該方法時沒有使用參數，將按字母順序對數組中的元素進行排序，說得更精確點，是按照字符編碼的順序進行排序。
  • Leetcode刷題-排序
    本文先介紹幾種常見的排序算法的python實現，接著對幾道涉及排序的leetcode題目進行實踐常見的排序算法冒泡排序進行n（數組長度n）次循環，每次從左向右兩個數依次比較，然後將未排序的最大值移到最右時間複雜度：O(n^2)  空間複雜度
  • Excel – 多條件排序就用 sortby 函數
    O365 這次出了兩個排序函數，除了前段時間給大家講解過的 sort 以外，還有一個 sortby 函數。sortby 函數也是用於排序，功能跟 sort 類似，主要區別在於：有關 sort 函數的詳解，請參閱 Excel – 告別繁瑣的菜單操作
  • Excel – 告別繁瑣的菜單操作,用 sort 函數排序
    今天再給大家介紹 O365 的一個新函數 sort，毫不誇張地說，在 Excel 升級到新版本之前，sort 是我最為期待的新函數之一。以下操作原本都要通過菜單來實現，自從 sort 函數問世之後，簡直太方便了：對某一列排序按照某一列，對整個數據表排序對任意部分列排序
  • Javascript中 Array.sort 原理學習
    其實在代碼中一個sort()就可以解決,並且時間複雜度和空間複雜度相對都不會過高。其實sort()不光可以對數組進行排序, 基本數據類型的數組都可以, 並且可以實現對對象數組的排序。這個sort其實遠比我們想像的更加智能，它會基於要排序的數據量選擇性能更加優秀的排序算法來實現排序。
  • 第89天:NumPy 排序和篩選函數
    對於數據分析來說，排序和篩選數據是不可或缺的一部分內容。NumPy 也提供了多種排序和篩選函數，本文就來介紹一下 NumPy 常見的排序和篩選函數。排序函數NumPy 中提供了排序相關的函數。排序函數已經幫助我們實現了不同的排序算法，我們只需要拿來直接使用就行。每個排序算法的執行速度，時間複雜度，空間複雜度和算法的穩定性都不相同，我們來看看常見的幾種排序算法的比較。
  • LeetCode-75.顏色分類(Sort Colors)
    顏色分類給定一個包含紅色、白色和藍色，一共 n 個元素的數組，原地對它們進行排序，使得相同顏色的元素相鄰，並按照紅色、白色、藍色順序排列。此題中，我們使用整數 0、 1 和 2 分別表示紅色、白色和藍色。注意:不能使用代碼庫中的排序函數來解決這道題。
  • PHP實現耐心排序(patience sort)算法
    耐心排序（patience sort）是一種排序算法，靈感來源於紙牌遊戲patience，並以此命名。該算法的一個變體可以有效地計算給定數組中最長遞增子序列的長度。該算法的名字來源於一個簡化版的patience紙牌遊戲。這個遊戲以一副洗牌開始。
  • JavaScript實現九種排序算法
    以前公司項目中對比過二分插入排序、優化冒泡排序、快速排序的JS實現執行時間，幾千條數據的數組在firefox下快速排序的速度比冒泡、插入排序快3至4秒（數組元素為複雜的對象，根據對象某一屬性值排序）。阮一峰老師研究JS實現排序時曾只針對該種排序進行講解：javascript的快速排序實現**。
  • C++ sort 排序函數用法
    ，以前老是寫冒泡，可把冒泡帶到OJ裡後發現經常超時，所以本想用快排，可是很多學長推薦用sort函數，因為自己寫的快排寫不好真的沒有sort快，所以毅然決然選擇sort函數用法1、sort函數可以三個參數也可以兩個參數，必須的頭文件#include < algorithm>和using namespace std;2、它使用的排序方法是類似於快排的方法，時間複雜度為n
  • Python實現經典排序算法,再也不怕面試官讓我手寫快排了!
    在Python中實現冒泡排序這是Python中冒泡排序算法的實現：def bubble_sort(array):     n = len(array)      for i in range(n):冒泡排序過程測算冒泡算法的大O運行複雜度冒泡排序的實現由兩個嵌套for循環組成，其中算法先執行n-1個比較，然後進行n-2個比較，依此類推，直到完成最終比較。
  • PHP中數組元素升序、降序及重新排序的函數
    range()函數還具有第三個參數，該參數的作用是設定步長，比如range(1,9,3)創建的數組元素是：1、4、72、PHP中常規數組的排序一般數組中的各元素均以字符或數字表現的，所以可對數組元素進行升序排列，該功能函數為sort()。
  • PHP數組排序函數大全
    介紹在眾多數組排序函數中,最常用的排序函數：sort、rsort、asort、arsort。主要區別1.有些函數基於 array 的鍵來排序，而其他的基於值來排序的：$array['key'] = 'value';。
  • [LeetCode] 937. Reorder Data in Log Files 日誌文件的重新排序
    You have an array of logs.
  • Pandas學習之旅:排序函數sort_values()
    pandas中的sort_values()函數原理類似於SQL中的order by，可以將數據集依照某個欄位中的數據進行排序，該函數即可根據指定列數據也可根據指定行的數據排序
  • 用Python手寫五大經典排序算法,看完這篇終於懂了!
    在Python中實現冒泡排序這是Python中冒泡排序算法的實現：def bubble_sort(array):     n = len(array)      for i in range(n):假設使用bubble_sort()排序，下圖說明了算法每次迭代時數組的實際換件情況：冒泡排序過程測算冒泡算法的大O運行複雜度冒泡排序的實現由兩個嵌套for循環組成，其中算法先執行n-1個比較，然後進行n-2個比較，依此類推，直到完成最終比較。
  • python中排序函數sort,sorted和operator.itemgetter的使用
    1.sort    sort()是Python列表的一個內置的排序方法，list.sort()
  • 淺談JavaScript 中 sort( ) 排序的坑
    基本排序JS 中的 Array 對象有一個排序方法 sort( )，調用它的運行結果一般來說是這樣的：甚至當數組中出現未定義值的元素時 sort( ) 也同樣好用。文檔中有這樣一句話：「所有未定義的數組元素都會被轉化成字符串，並通過比較 UTF-16 的值來進行排序。」
  • 我用Python之sort排序
    大學C語言編程課上，老師只介紹了最符合直觀思維，效率很低的冒泡排序，經典的快速排序也沒介紹（不過這不是老師的錯，修行在個人）。C++ 的標準模板類庫 STL 提供了快速排序函數 qsort 。但為了實現對自定義類、結構體的排序操作，通常需要自己另寫比較函數，代碼量較大，編程效率較低。「人生苦短，我用Python「。