In this paper a novel scheme for video denoising using nonlocal mean algorithm is proposed. In contrast to the traditional methods, the proposed scheme uses the mean absolute difference (MAD) of the current pixel block and the candidate blocks both in spatial and temporal domain as a pre-selecting criterion. At the same time, rather than one single pixel, this scheme reconstructs a block with different number of pixels according to the statistic property of the current pixel block, which dramatically lowers the computational burden and keeps good denoising performance. Several methods used in this algorithm share high similarity with the video encoding techniques today, and this algorithm is especially suitable to implement those video processing methods combined with video encoder.