题解 | #扑克牌顺子,最优解时间复杂度O(n)，空间复杂度O(1)#

最优解时间复杂度O(n)，空间复杂度O(1)

关键点：

如何在O(n)的时间复杂度，O(1)的空间复杂度内判断数组是否有重复元素？

对于已知最大值和最小值的数组，我们将array[i]的元素放到array[i] - 1的位置上，但是本题中数组大小只能是5，所以咱们array[i]放的位置就是array[i] % 5，比如，3，8，13都在数组下标为3的这个位置上，5,10都在0这个位置上。只要array[array[i] % 5] % 5 == array[i] % 5 && i != array[i] % 5，就代表同一个位置，出现了相同的元素

举例如下

当i == 0会发生3轮交换

1,2,6,4,3

第一轮交换 array[i] == 1

2,1,6,4,3

第二轮交换 array[i] == 2

6,1,2,4,3

第三轮交换 array[i] == 6 满足 array[6 % 5] % 5 == 6 % 5 && i != 6 % 5

虽然1和6实际不相等，但是对于扑克牌顺子这个题来说，只要max-min大于4其实也就不是顺子了，所以这个地方可以直接返回false

具体代码如下

if (numbers == null || numbers.length < 5) {
            return false;
        }
        int min = 13;
        int max = 0;
        int spNumber = 5;
        for (int i = 0; i < numbers.length; ++i) {
            // 将每个数字放到自己的位置上
            int num = numbers[i];
            if (num == 0) {
                continue;
            }
            if (num < min) {
                min = num;
            }
            if (num > max) {
                max = num;
            }
            if (numbers[num % spNumber] == num % spNumber && (num % spNumber) != i && numbers[num % spNumber] != 0) {
                // 发现了重复的元素
                return false;
            }
            while (i != numbers[i] % spNumber) {
                int temp = numbers[numbers[i] % spNumber];
                if (numbers[i] == 0) {
                    break;
                }
                if (temp % spNumber == numbers[i] % spNumber && temp != 0 && numbers[i] != 0) {
                    // 交换过程中发现了重复元素
                    return false;
                }
                numbers[numbers[i] % spNumber] = numbers[i];
                numbers[i] = temp;
            }
        }
        if (max - min <= 4) {
            return true;
        }
        return false;