สมมติว่าบางคนจะขอเป็นเพื่อน เรารู้อายุของพวกเขา สิ่งเหล่านี้ถูกเก็บไว้ในวัย[i] นี่แสดงว่าอายุของบุคคลนั้น ตอนนี้ A จะไม่ขอเป็นเพื่อนกับบุคคล B (B !=A) หากเงื่อนไขใด ๆ ต่อไปนี้เป็นจริง -
- อายุ[B] <=0.5 * อายุ[A] + 7
- อายุ[B]>อายุ[A]
- อายุ[B]> 100 &&อายุ[A] <100
มิฉะนั้น A จะขอเป็นเพื่อน B. คุณสามารถพิจารณาว่าถ้า A ขอ B, B ไม่จำเป็นต้องขอ A. และคนจะไม่ขอเป็นเพื่อนเอง เราจึงต้องหาว่ามีการขอเป็นเพื่อนทั้งหมดกี่คน?
สมมติว่าอาร์เรย์อายุเท่ากับ [16,17,18] ผลลัพธ์จะเป็น 2 เนื่องจากคำขอจะเป็น 17 -> 16, 18 -> 17
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดที่เก็บข้อมูลอาร์เรย์ขนาด 1000 จากนั้นเก็บความถี่ขององค์ประกอบอาร์เรย์อายุไว้ในที่เก็บข้อมูล
- จากนั้นค้นหาและจัดเก็บผลรวมขององค์ประกอบที่เก็บข้อมูลไว้ในที่เก็บข้อมูล
- ret :=0
- สำหรับฉันอยู่ในช่วง 0 ถึงขนาดอาร์เรย์อายุ – 1
- x :=อายุ[i], y :=(อายุ[i] / 2) + 7
- ถ้า x>=y แล้ว
- ret :=bucket[x] – bucket[y]
- ถ้า bucket[x] – bucket[y] ไม่ใช่ศูนย์ ให้ลดการ ret ลง 1
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numFriendRequests(vector<int>& ages) {
vector <int> bucket(1000);
for(int i = 0; i < ages.size(); i++){
bucket[ages[i]]++;
}
for(int i = 1; i < 1000; i++)bucket[i] += bucket[i - 1];
int ret = 0;
for(int i = 0; i < ages.size(); i++){
int x = ages[i];
int y = ((ages[i]) / 2) + 7;
if(x >= y){
ret += (bucket[x] - bucket[y]);
if((bucket[x] - bucket[y]))
ret--;
}
}
return ret;
}
};
main(){
vector<int> v1 = {16, 17, 18};
Solution ob;
cout << (ob.numFriendRequests(v1));
} อินพุต
[16,17,18]
ผลลัพธ์
2
