Given an array A of n elements and a number 0<=k<=n, return a subset of A of size k .
Example
Input: A = [5, 11, 3, 7], k =3
Output: [3, 7, 11]
Note that there is no fixed output. It might vary for each run.
Solution
Idea:
Choose samples one by one
For each sample, choose a random integer which indicates the location, then swap this element to the beginning of the array
Time complexity: O(k)
Space complexity: O(1)
import(random)defrandom_sampling(A,k):for i inrange(k):# generate a random number from i to len(A)-1 j = random.randint(i, len(A)-1) A[i], A[j]= A[j], A[i]return A[:k]