Resolving the ambiguity in both range and velocity domain is one of the essential issues for the pulse Doppler (PD) radars using medium pulse repetition frequency (PRF) waveforms. The existing solutions are mainly based on the Chinese Remainder Theorem (CRT) and its variations and extensions, but these algorithms typically have an unsatisfactory accuracy and are highly complex in computation, especially for the case of a large false-alarm rate. In this work, we proposed a new approach to tackle with ambiguity based on the partial distance matrices (PDM) and implemented it on the NVIDIA graphics processing unit (GPU) platform. The evaluations based on both Monte-Carlo simulations and real measured data present the advantages of the proposed approach in accuracy and efficiency. The results also show the proposed approach can be utilized as a real-time algorithm even for a low-threshold detection scheme.