leetcode 382) Linked List Random Node

LV. Medium 🧐

https://leetcode.com/problems/linked-list-random-node/

Linked List Random Node - LeetCode

 

문제

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

Implement the Solution class:

• Solution(ListNode head) Initializes the object with the integer array nums.
• int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen.

 

Example 1:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

 

Constraints:

• The number of nodes in the linked list will be in the range [1, 104].
• -104 <= Node.val <= 104
• At most 104 calls will be made to getRandom.

Follow up:

• What if the linked list is extremely large and its length is unknown to you?
• Could you solve this efficiently without using extra space?

 

문제 해결법

explanation를 보면 처음에 객체 생성을 해주고, 그 후에는 getRandom() 함수만 호출한다

그래서 처음 객체를 생성할 때 val를 vector에 저장해 놓으면 getRandom() 함수에서 시간을 단축시킬 수 있겠다는 생각이 듦!

 

Solution() constructor에서 vector에 _val 값을 저장해주고, vector의 사이즈도 저장한다

getRandom()가 호출되었을 때에는 #include <cstdlib>에 있는 rand()를 통해 랜덤 값을 받아와

valSize로 나눠 난수의 범위 = 0 ~ valSize로 바꿔준다

valSize 인덱스에 있는 val 값을 리턴하면 끝!!!

 

해결 코드

class Solution {
private:
	vector<int> _val;
	int _valSize;

public:
	Solution(ListNode *head) {
		_valSize = 0;
		srand(5323);
		while (head) {
			_val.push_back(head->val);
			head = head->next;
			_valSize++;
		}
	}
	int getRandom() {
		return _val[rand() % _valSize];
	}
};