Given 3 arrays, pick 3 nos, one from each array, say a,b,c such that |a-b|+|b-c|+|c-a| is minimum

如果假設(shè)a >=b >= c, 就是求2（a-c）, 也就是說最終的值只與最大值和最小值有關(guān)

我的想法是將這三個(gè)數(shù)組的元素加上所屬數(shù)組類別的信息，然后進(jìn)行排序，下面的工作就是和最短鏈珠的做法一樣了，依次找出包含a,b,c數(shù)組元素的最小span，然后計(jì)算這個(gè)span最大值和最小值之差。

網(wǎng)上的做法更為精巧，整個(gè)是3數(shù)組歸并的過程。首先計(jì)算三元組(ai,bj,ck)的值，然后找出三元組中最小的元素，然后將這個(gè)最小元素所屬的數(shù)組的指針加1.

可以用反證法證明上述思路，設(shè) ai >= bj >= ck

如果j++, 那么獲得的新的三元組的值大于等于之前的三元組

如果i++，那么獲得的新的三元組的值大于等于之前的三元組

所以只有k++, 才有可能獲得的新元祖的值小于之前的三元組

int CalcABS(int a, int b, int c) {return abs(a-b) + abs(a-c) + abs(b-c); }int GetMin(vector<int>& vec) {assert(!vec.empty());int nMin = vec[0];for (int i = 0; i < vec.size(); i++){if (vec[i] < nMin)nMin = vec[i];}return nMin; }int GetABC(int a[], int na, int b[], int nb, int c[], int nc, int& sa, int& sb, int& sc) {assert(a && na>0 && b && nb>0 && c && nc>0);sort(a, a+na);sort(b, b+nb);sort(c, c+nc);int i = 0;int j = 0;int k = 0;sa = sb = sc = 0;int nMin = CalcABS(a[i], b[j], c[k]);while (i != na-1 || j != nb-1 || k != nc-1)//應(yīng)該用&&連接{vector<int> vec;if (i != na-1) vec.push_back(a[i]);if (j != nb-1) vec.push_back(b[j]);if (k != nc-1) vec.push_back(c[k]);int nRes = GetMin(vec);if (i != na-1 && a[i] == nRes)i++;else if (j != nb-1 && b[j] == nRes)j++;else k++;nRes = CalcABS(a[i], b[j], c[k]);if (nRes < nMin){sa = a[i];sb = b[j];sc = c[k];nMin = nRes;}}return nMin; }

總結(jié)

以上是生活随笔為你收集整理的从三个数组中选择满足条件的三个数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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