To stop it from happening in the future go into Gmail settings online (not your phone), about 1/3 way down is "Create contacts for auto-complete:". Set it to "I'll add contacts myself". This will cut way down on what's searchable for auto-complete.

Then go into all contacts online, you should be able to find/delete them there.

After you do that, go into settings/apps on your phone and find Gmail. Clear cache. Then re-sync them, hat should update your contacts to with only your good ones.