剑指offer 寻找文件副本

题目描述

题目链接

思路一

遍历数组中每一个元素，在加入set之前判断是否存在当前元素，若存在则返回该值。
将当前元素添加到set中

class Solution {
    public int findRepeatDocument(int[] documents){
        // set解法，加入的时候判断是否存在该运算，若存在则找到一个重复的
         
         Set<Integer> set = new HashSet<>();
         for(Integer ele: documents){
             if(set.contains(ele))
                 return ele;
             set.add(ele);
         }
      
       return -1;        
    }
}

思路二 抽屉原理

抽屉原理，即将元素的值和它对应的下标对应起来，比如5就放到索引为5的位置，即nums[5]

如果i = nums[i] 则不用交换
若i!=nums[i]那么就需要交换，索引从0开始
假设数组中的元素是
4 2 3 4 0
4(nums[0])和nums[4]的元素进行交换，即将4和0交换,此时i=0
0 2 3 4 4
此时nums[0] = 0, nums[4] = 4，i=nums[i]成立

2(nums[1])和nums[2]互换，此时i=1
0 3 2 4 4
3(nums[1])和nums[3]互换，此时i=1
0 4 2 3 4
4(nums[1])和nums[4]互换，但此时发现4==nums[4]找到重复元素，返回

• 若i=nums[i]则继续
• 若i!=nums[i]
  - 将nums[i]和nums[nums[i]]互换，互换之前判断一下nums[i]是否等于nums[nums[i]]若等于则返回，若不等于就将nums[i]和nums[nums[i]]互换，直到nums[i]=nums[nums[i]]为止

 for(int i = 0; i < documents.length; i++){
           while (i != documents[i]){
               if(documents[i] == documents[documents[i]])
                   return documents[i];
               int k = documents[documents[i]];
               documents[documents[i]] = documents[i];
               documents[i] = k;
           }
       }

原文地址：https://blog.csdn.net/qq_45418837/article/details/145140217

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！