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

共以下 5 个回答

• 王位詮釋 普通 2024年4月15日 下午2:09

  哈希表法：
  class Solution {
      public int findRepeatDocument(int[] documents) {
          Set<Integer> set = new HashSet<>();
          for(int i=0;i<documents.length;i++){
              if(set.contains(documents[i])){
                  return documents[i];
              }else{
                  set.add(documents[i]);
              }
          }
          return -1;
      }
  }
  时间复杂度：O(n)
  空间复杂度：O(n)
  

  排序法：
  class Solution {
      public int findRepeatDocument(int[] documents) {
          Arrays.sort(documents);
          for(int i=1;i<documents.length;i++){
              if(documents[i]==documents[i-1]){
                  return documents[i];
              }
          }
          return -1;
      }
  }
  时间复杂度：O(nlogn)
  空间复杂度：O(1)
  

  下标法：
  class Solution {
      public int findRepeatDocument(int[] documents) {
          int i = 0;
          while(i<documents.length){
              if(documents[i]==i){
                  i++;
                  continue;
              }
              if(documents[documents[i]]==documents[i]){//多个元素对应同一个下标
                  return documents[i];
              }
              int temp = documents[i];
              documents[i] = documents[temp];
              documents[temp] = temp;
          }
          return -1;
      }
  }
  时间复杂度：O(n)
  空间复杂度：O(1)
  

  0 赞同 0 条回复

  登录以回复
• 白雪公主倒拔垂杨柳 永久会员 2024年4月10日 下午3:21

  • 哈希表的方法

  class Solution {
      public int findRepeatDocument(int[] documents) {
  
          Map<Integer, Integer> countMap = new HashMap<>();
  
          for (int document : documents) {
              countMap.put(document, countMap.getOrDefault(document, 0) + 1);
  
              if(countMap.get(document)>1) return document;
          }
  
          return -1;
      }
  }
  

  时间复杂度o(n),空间复杂度o(n)

  • 文件id的范围是0-(n-1)，利用这一点,可以采用坐标法

  class Solution {
      public int findRepeatDocument(int[] documents) {
  
          for(int i=0;i<documents.length;i++){
              while(documents[i]!=i){
                  if(documents[i]==documents[documents[i]]) return documents[i];
  
                  int k = documents[documents[i]];
                  documents[documents[i]]=documents[i];
                  documents[i]=k;
              }
          }
  
          return -1;
      }
  }
  

  时间复杂度：O(n)
  额外空间复杂度：O(1)

  0 赞同 0 条回复

  登录以回复
• 云无深雁影 普通 2024年4月9日 下午9:11

  class Solution {
  public int findRepeatDocument(int[] documents) {
  int cur = 0;
  while(cur < documents.length){
  if(documents[cur] cur){
  cur++;
  continue;
  }
  if(documents[documents[cur]] documents[cur])
  return documents[cur];
  int temp = documents[documents[cur]];
  documents[documents[cur]] = documents[cur];
  documents[cur] = temp;
  }
  return -1;
  }
  }
  //时间复杂度On
  //空间复杂度O1

  0 赞同 0 条回复

  登录以回复
• Jimmy 普通 2024年4月8日 下午10:24

  哈希

  class Solution {
  public:
      int findRepeatDocument(vector<int>& documents) {
          unordered_map<int,int> map;
          for(int x:documents)
          {
              map[x]++;
              if(map[x] > 1)
              return x;
          }
          return -1;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 紫芝 普通 2024年4月5日 下午8:38

  时间：O(n)
  空间：O(1)

  “`c++
  class Solution {
  public:
  int findRepeatDocument(vector& documents) {
  for (int i=0; i

  0 赞同 0 条回复

  登录以回复