一个整形数组,长为n,元素范围为1~(n-1),则这个数组内至少有一个数字出现多次,现在要求用O(n)时间,O(1)空间找出一个出现多次的数。 以下为原文: here’s one I got asked which kicked my butt. Write a function that takes in an array of n ints from 1…n-1. For example, an array of 4 numbers which all have values of 1, 2, or 3. There will obviously be at least one duplicate number. Return one of the duplicates (EASY!) – Now do this in order n, without allocating ANY new memory (no hash table or anything).. (Note: I did figure out a solution to this, but the interview didn’t seem to like it very much but whatever)..read more