【杂题】剑指 Offer 03. 数组中重复的数字

共以下 3 个回答

• 陆狗陆狗 普通 2025年1月7日 下午9:40

  解题思路
  – 最简单的思路是使用HashMap，但是需要额外的空间
  – 优化就是使用0 ≤ documents[i] ≤ n-1的特性，用原数组进行一些重复性的校验
  – 判断当前index=documents[index]
  – 不相等，就把当前documents[index]换到正确的下标处，如果那个下标已经有相等的占据了，就说明重复了（如果是完全不重复的，那么理论上可以遍历到最后一个）
  【题解1】

  class Solution {
      public int findRepeatDocument(int[] documents) {
  
          int i = 0;
          while (i < documents.length) {
              // 判断当前index=documents[index]
              // 不相等，就把当前documents[index]换到正确的下标处，如果那个下标已经有相等的占据了，就说明重复了
              int curValue = documents[i];
              while (curValue != i) {
                  if (documents[curValue] == curValue) {
                      return curValue;
                  } else {
                      swap(documents, i, curValue);
                  }
                  curValue = documents[i];
              }
              i++;
          }
          return -1;
      }
  
      public void swap(int[] documents, int a, int b) {
          int tmpt = documents[a];
          documents[a] = documents[b];
          documents[b] = tmpt;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• Aatorx 永久会员 2024年12月30日 下午3:03

  class Solution {
  public:
      int findRepeatDocument(vector<int>& documents) {
          int res = 0;
          while(res < documents.size()) {
              if(documents[res] == res) {
                  res++;
                  continue;
              }
              if(documents[documents[res]] == documents[res]) {
                  return documents[res];
              }
              swap(documents[documents[res]], documents[res]);
          }
          return -1;
      }
  };
  

  原地交换法，时间复杂度O(N)，空间复杂度O(1)。

  0 赞同 0 条回复

  登录以回复
• 晓宇 普通 2024年12月28日 下午6:53

  // 下标交换
  class Solution {
  public:
      int findRepeatDocument(vector<int>& documents) {
          for(int i = 0;i < documents.size();i++){
              while(i != documents[i]){ // 多个元素对应同一个下标
                  if(documents[i] == documents[documents[i]]){
                      return documents[i];
                  }
                  // document[i] document[document[i]] 将元素换到正确位置
                  int k = documents[documents[i]];
                  documents[documents[i]] = documents[i];
                  documents[i] = k;
              }
          }
          return -1;
      }
      // o1 on
  };
  

  0 赞同 0 条回复

  登录以回复