力扣之数组篇物归原主法秒杀 448 442 41

╰+攻爆jí腚メ 2022-11-17 14:34 163阅读 0赞

# 一、前言 #

1.物归原主法  
给定一数组，其长度为n，其元素a\[i\] ∈ \[ 0 , n − 1 \] \\in\[0, n - 1\] ∈\[0,n−1\]时，当我们把a\[i\]放到`i = a[i]`的位置时，那些重复的数值即会出现在a\[i\] != i的位置处。

> 例子：\[2, 3, 1, 0, 2, 5, 3\]; 物归原主后：\[0, 1, 2, 3, 2, 5, 3\]。  
> 可见，重复的数字：2在i = 4处，3在i = 6处。

> 当然了，有的题目做了点变体，即a\[i\] ∈ \[ 1 , n \] \\in\[1, n\] ∈\[1,n\]时，则把a\[i\]放到`i = a[i] - 1`的位置上。  
> 例如：1放到i = 0的位置上

> 物归原主法见下文“二、2.代码”，核心思想：**没放对**(nums\[i\] != i)并且**非重复**(nums\[nums\[i\]\] != nums\[i\])**便交换**。

# 二、物归原主法的思想来源 #

0.《剑指offer》面试题3：数组中重复的数字

1.[题目][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]  
2.代码（java）

class Solution {
        
        public int findRepeatNumber(int[] nums) {
        
            int res = -1;
            for(int i = 0; i < nums.length; i++) {
        
                while(nums[i] != i && nums[nums[i]] != nums[i]) {
        
                    //swap(nums[i], nums[nums[i]]);
                    int tmp = nums[i];
                    nums[i] = nums[tmp];
                    nums[tmp] = tmp;
                }
            }
            for(int i = 0; i < nums.length; i++) {
        
                if(nums[i] != i) {
        
                    res = nums[i];
                    break;
                }
            }
            return res;
        }
    }

> 物归原主法：first blood !

# 三、秒杀力扣3道题 #

## 1.[448][] ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70 1]

*  **代码（java）**

class Solution {
        
        public List<Integer> findDisappearedNumbers(int[] nums) {
        
            List<Integer> res = new ArrayList<>();
            for(int i = 0; i < nums.length; i++) {
        
                while(nums[i] - 1 != i && nums[nums[i] - 1] != nums[i]) {
        
                    //swap(nums[i], nums[nums[i] - 1])
                    int tmp = nums[i];
                    nums[i] = nums[tmp - 1];
                    nums[tmp - 1] = tmp;
                }
            }
            for(int i = 0; i < nums.length; i++) {
        
                if(nums[i] - 1 != i)
                    res.add(i + 1);
            }
            return res;
        }
    }

> 和**剑指 Offer 03**几乎一致，物归原主法：double kill !

## 2.[442][] ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70 2]

*  **代码（java）**

class Solution {
        
        public List<Integer> findDuplicates(int[] nums) {
        
            List<Integer> res = new ArrayList<>();
            for(int i = 0; i < nums.length; i++) {
        
                while(nums[i] - 1 != i && nums[nums[i] - 1] != nums[i]) {
        
                    //swap(nums[i], nums[nums[i] - 1]);
                    int tmp = nums[i];
                    nums[i] = nums[tmp - 1];
                    nums[tmp - 1] = tmp;
                }
            }
            for(int i = 0; i < nums.length; i++) {
        
                if(nums[i] - 1 != i) {
        
                    res.add(nums[i]);
                }
            }
            return res;
        }
    }

> 和**剑指 Offer 03**几乎一致，物归原主法：triple kill !

## 3.[41][] ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70 3]

*  **代码（java）**

class Solution {
        
        public int firstMissingPositive(int[] nums) {
        
            for(int i = 0; i < nums.length; i++) {
        
                while(nums[i] > 0 && nums[i] < nums.length && nums[i] - 1 != i && nums[nums[i] - 1] != nums[i]) {
        
                    //swap(nums[i], nums[nums[i] - 1]);
                    int tmp = nums[i];
                    nums[i] = nums[tmp - 1];
                    nums[tmp - 1] = tmp;
                }
            }
            for(int i = 0; i < nums.length; i++) {
        
                if(nums[i] - 1 != i) {
        
                    return i + 1;
                }
            }
            return nums.length + 1;
    
        }
    }

> 和**剑指 Offer 03**几乎一致，物归原主法：quadra kill !

> 之前的题目都和重复数字有关系，这道题好像和重复数字没关系，怎么也可以用物归原主法来秒杀呢？  
> 因为物归原主法的本质是`通过下标处放置的数值来判断某数字是否存在。`  
> 本题要寻找没有出现的最小正整数，显然就是判断从`1`起的正整数是否存在。  
> 如果`nums[i] - 1 == i`，比如：i = 0，则说明，1存在。

[Link 1]: https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]: /images/20221022/077c4ab9897b4daea44604241568fc93.png
[448]: https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/63d0c86634554e19ade8ce393e15eae3.png
[442]: https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/submissions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70 2]: /images/20221022/9bbe5a39c7ff42dbbd5f87301283064e.png
[41]: https://leetcode-cn.com/problems/first-missing-positive/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70 3]: /images/20221022/5b0fdb6446444f568f53675806491125.png