文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 暴力超時(shí)
    • 2.2 優(yōu)化

1. 題目

給定 m 個(gè)數(shù)組，每個(gè)數(shù)組都已經(jīng)按照升序排好序了。
現(xiàn)在你需要從兩個(gè)不同的數(shù)組中選擇兩個(gè)整數(shù)（每個(gè)數(shù)組選一個(gè)）并且計(jì)算它們的距離。
兩個(gè)整數(shù) a 和 b 之間的距離定義為它們差的絕對(duì)值 |a-b| 。你的任務(wù)就是去找到最大距離

示例 1： 輸入： [[1,2,3],[4,5],[1,2,3]] 輸出： 4 解釋： 一種得到答案 4 的方法是從第一個(gè)數(shù)組或者第三個(gè)數(shù)組中選擇 1， 同時(shí)從第二個(gè)數(shù)組中選擇 5 。注意： 每個(gè)給定數(shù)組至少會(huì)有 1 個(gè)數(shù)字。列表中至少有兩個(gè)非空數(shù)組。 所有 m 個(gè)數(shù)組中的數(shù)字總數(shù)目在范圍 [2, 10000] 內(nèi)。 m 個(gè)數(shù)組中所有整數(shù)的范圍在 [-10000, 10000] 內(nèi)。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-distance-in-arrays
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

2.1 暴力超時(shí)

120 / 124 個(gè)通過(guò)測(cè)試用例

class Solution { public:int maxDistance(vector<vector<int>>& arrays) {int i, j, maxdis = 0, n = arrays.size();for(i = 0; i < n; ++i){for(j = i+1; j < n; ++j){maxdis = max(maxdis, abs(arrays[i].front()-arrays[j].back()));maxdis = max(maxdis, abs(arrays[j].front()-arrays[i].back()));}}return maxdis;} };

2.2 優(yōu)化

• 判斷過(guò)了的數(shù)組，可以進(jìn)行合并，只有合并以后的 最大的值，最小的值 起作用

class Solution { public:int maxDistance(vector<vector<int>>& arrays) {int i, j, maxdis = 0, n = arrays.size();int MAX = arrays[0].back(), MIN = arrays[0].front();for(i = 1; i < n; ++i){maxdis = max(maxdis, abs(arrays[i].front()-MAX));maxdis = max(maxdis, abs(arrays[i].back()-MIN));MIN = min(MIN, arrays[i].front());MAX = max(MAX, arrays[i].back());}return maxdis;} };

56 ms 16.5 MB

---

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)，一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 624. 数组列表中的最大距离的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。