สมมติว่าเรามีรายการของสี่เหลี่ยมที่มีการจัดแนวแกนที่ไม่ทับซ้อนกัน เราต้องเขียนการเลือกฟังก์ชันที่สุ่มเลือกตัวเลขจำนวนเต็มแบบสุ่มและสม่ำเสมอ ชี้ในช่องว่างที่ครอบคลุมโดยรูปสี่เหลี่ยมผืนผ้า ดังนั้นเราต้องจำไว้บางประเด็น -
- จุดจำนวนเต็มเป็นจุดที่มีพิกัดจำนวนเต็ม
- จุดบนเส้นรอบวงของสี่เหลี่ยมผืนผ้ารวมอยู่ในช่องว่างที่รูปสี่เหลี่ยมผืนผ้าปิดไว้
- สี่เหลี่ยมผืนผ้า ith =rects[i] หมายถึง [x1,y1,x2,y2] โดยที่ [x1, y1] เป็นพิกัดจำนวนเต็มของมุมล่างซ้าย และ [x2, y2] เป็นพิกัดจำนวนเต็มของ มุมบนขวา
- ความยาวและความกว้างของสี่เหลี่ยมแต่ละอันไม่เกิน 2000
- 1 <=rects.length <=100
- เลือกจุดกลับเป็นอาร์เรย์ของพิกัดจำนวนเต็ม [p_x, p_y]
หากอินพุตเป็น [1,1,5,5] และเราเรียก pick() สามครั้ง ผลลัพธ์จะเป็น [4,1], [4,1], [3,3]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างพื้นที่สองอาร์เรย์และเรียง
- ใน initializer ให้ทำดังนี้ -
- rect :=rects, sum :=0
- สำหรับ i ในช่วง 0 ถึงขนาดของ rects – 1
- (x1, y1) :=(rects[i, 0], rects[i, 1])
- (x2, y2) :=(rects[i, 2], rects[i, 3])
- อุณหภูมิ :=|x2 – x1 + 1| * |y2 – y1 + 1|
- sum :=sum + temp และใส่ผลรวมลงในพื้นที่
- ในวิธีการหยิบ ให้ทำดังต่อไปนี้ −
- randArea :=สุ่มจำนวน mod sum + 1
- สำหรับ i ในช่วง 0 ถึงขนาดของพื้นที่ – 1
- ถ้า randArea <=area[i] แล้วออกมาจากลูป
- dist_x :=ตัวดัดแปลงตัวเลขสุ่ม |rect[i,0] – rect[i,2] + 1|
- dist_y :=ตัวดัดแปลงตัวเลขสุ่ม |rect[i,1] – rect[i,3] + 1|
- ส่งคืนคู่ (dist_x + rect[i, 0], dist_y + rect[i, 1])
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector <int> area;
vector < vector <int> > rect;
int sum;
Solution(vector<vector<int> >& rects) {
rect = rects;
sum = 0;
for(int i =0 ; i < rects.size(); i++){
int x1 = rects[i][0];
int y1 = rects[i][1];
int x2 = rects[i][2];
int y2 = rects[i][3];
int temp = (abs(x2 - x1) + 1) * (abs(y2 - y1) + 1);
sum += temp;
area.push_back(sum);
}
}
vector<int> pick() {
int randArea = rand() % sum + 1;
int i;
for(i = 0; i < area.size(); i++){
if(randArea <= area[i]) break;
}
int dist_x = rand() % (abs(rect[i][0] - rect[i][2] ) + 1);
int dist_y = rand() % (abs(rect[i][1] - rect[i][3] ) + 1);
return {dist_x + rect[i][0], dist_y + rect[i][1]};
}
};
main(){
vector<vector<int> > v = {{1, 1, 5, 5}};
Solution ob(v);
print_vector(ob.pick());
print_vector(ob.pick());
print_vector(ob.pick());
} อินพุต
["Solution", "pick", "pick", "pick"] [[[[1, 1, 5, 5]]], [], [], []]
ผลลัพธ์
[2, 3, ] [4, 1, ] [3, 5, ]
