Possible Duplicate:
Unique random numbers in O(1)?
How do I fill an integer array with unique values (no duplicates) in C?
int vektor[10];
for (i = 0; i < 10; i++) {
vektor[i] = rand() % 100 + 1;
}
//No uniqueness here
Here is an O(M) average-time method.
Method: If M <= N/2, use procedure S(M,N) (below) to generate result array R, and return R. If M > N/2, use procedure S(N-M,N) to generate R, then compute X = {1..M}\R [the complement of R in {1..M}], shuffle X with Fisher-Yates shuffle [in time O(M)], and return X.
In the M > N/2 case, where O(M) == O(N), there are several fast ways to compute the complement. In the code shown below, for brevity I have only included an example of procedure S(M,N) coded inline in main(). Fisher-Yates shuffle is O(M) and is illustrated in main answer to related question #196017. Other previous related questions: #158716 and #54059.
The reason that S(M,N) takes O(M) time instead of O(N) time when M < N/2 is that, as described in Coupon-collector's problem the expectation E(t_k) is kH_k, from which E(t_{k/2}) = k(H_k - H_{k/2}) or about k*(ln(k)-ln(k/2)+O(1)) = k*(ln(k/(k/2))+O(1)) = k*(ln(2)+O(1)) = O(k).
Procedure S(k,N): [The body of this procedure is the dozen lines after the comment "Gen M distinct random numbers" in the code below.] Allocate and initialize three M+1-element integer arrays H, L, and V to all -1 values. For i=0 to M-1: Put a random value v into V[i] and into the sentinel node V[-1]. Get one of M list heads from H[v%M] and follow that list until finding a match to v. If the match is at V[-1] then v is a new value; so update l