1. 題目

某交友網站會給除了第一個用戶以外的每個新注冊的用戶推薦一位之前已經注冊過并且性格值和他最相近的用戶，如果有多人滿足條件則選擇性格值較小的。

給定數組val[]表示按時間順序注冊的 n 位用戶的性格值，輸出一個大小為 n-1 的數組，表示系統給這些人推薦的用戶的性格值。

樣例 1: 輸入: val=[8,9,7,3,0,5,11] 輸出: [8,8,7,3,3,9] 解釋: 令 ans = [] 第 2 個數為 9，前面只有第 1 個數 8，此時 ans = [8] 第 3 個數為 7，前面的數有 8, 9，與 7 性格值最小的為 8，此時 ans = [8, 8] 第 4 個數為 3，前面的數有 8, 9, 7，與 3 性格值最小的為 7，此時 ans = [8, 8, 7] 第 5 個數為 0，前面的數有 8, 9, 7, 3，與 0 性格值最小的為 3，此時 ans = [8, 8, 7, 3] 第 6 個數為 5，前面的數有 8, 9, 7, 3, 0，與 5 性格值最小的為 3，此時 ans = [8, 8, 7, 3, 3] 第 7 個數為 11，前面的數有 8, 9, 7, 3, 0, 5，與 11 性格值最小的為 9，此時 ans = [8, 8, 7, 3, 3, 9]樣例 2: 輸入: val=[465, 5464, 6467, 6466779, 6461, 56] 輸出: [465,5464,6467,6467,465] 解釋: 令 ans = [] 第 2 個數為 5464，前面只有第 1 個數 465，此時 ans = [465] 第 3 個數為 6467，前面的數有 465, 5464，與 6467 性格值最小的為 5464，此時 ans = [465, 5464] 第 4 個數為 6466779，前面的數有 465, 5464, 6467，與 6466779 性格值最小的為 6467，此時 ans = [465, 5464, 6467] 第 5 個數為 6461，前面的數有 465, 5464, 6467, 6466779，與 6461 性格值最小的為 6467，此時 ans = [465, 5464, 6467, 6467] 第 6 個數為 56，前面的數有 465, 5464, 6467, 6466779, 6461，與 56 性格值最小的為 465，此時 ans =[465, 5464, 6467, 6467, 465]注意事項 2<=n<=100000 0<=val<=1000000

類似題目：LeetCode 315. 計算右側小于當前元素的個數（二叉查找樹&二分查找&歸并排序逆序數總結）

2. 解題

• 給一個空數組，依次把性格值二分插入到其中
• 檢查插入位置前后跟我 絕對值較小 的取為答案
• 變形版 二分查找請參考

class Solution {int l,r,mid; public:vector<int> getAns(vector<int> &val) {if(val.size() <= 1)return {};vector<int> t;//二分插入數組t.push_back(val[0]);vector<int> ans(val.size()-1);int i, idx, k = 0, f, b;for(i = 1; i < val.size(); i++,k++){idx = bs(t,val[i]);//插入位置t.insert(t.begin()+idx+1,val[i]);//插入數組f = (idx >= 0 ? t[idx] : -10000000);//前面的性格值b = (idx+2 < t.size() ? t[idx+2] : -10000000);//后面的性格值if(abs(f-val[i]) <= abs(b-val[i]))ans[k] = t[idx];//取較小的elseans[k] = t[idx+2];}return ans;}int bs(vector<int> & a, int& target){ //二分查找，性格值小于等我的 最后一個l = 0, r = a.size()-1;while(l <= r){mid = l+((r-l)>>1);if(a[mid] > target)r = mid-1;else //(a[mid] <= target){if(mid==a.size()-1 || a[mid+1] > target)return mid;elsel = mid+1;}}return -1;} };

100% 數據通過測試
總耗時 653 ms
您的提交打敗了 35.48% 的提交!

總結

以上是生活随笔為你收集整理的LintCode 1690. 朋友推荐（二分插入）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。