【剑指offer】数组中重复的数字

书上的思想真的很nice，时间O(n) 空间O(1)

public class Solution {

  public boolean duplicate(int numbers[], int length, int[] duplication) {
      if (length <= 0 || numbers == null) {
          return false;
      }

      int index = 0;
      while (index < length) {
          if (numbers[index] == index) { // 当前下标index的值刚好为index
              index++;
          } else {
              int tmp = numbers[index]; 
              if (tmp == numbers[tmp]) { // 要交换位置的两个数相同
                  duplication[0] = tmp;
                  return true;
              } else { // 交换位置
                  numbers[index] = numbers[tmp];
                  numbers[tmp] = tmp;
              }
          }
      }
      return false;
  }
}

讨论区BoTinker的思想，在原数组上通过+length的方式达到开标记数组的目的，思想很赞！！！ 时间O(n) 空间O(1)

public class Solution {

  public boolean duplicate(int numbers[], int length, int[] duplication) {
      if (length <= 0 || numbers == null) {
          return false;
      }

      for (int i = 0; i < length; i++) {
          int index = numbers[i];
          if (index >= length) {
              index -= length;
          }
          if (numbers[index] >= length) {
              duplication[0] = index;
              return true;
          }
          numbers[index] += length;

      }
      return false;
  }
}