[LeetCode] 448. Find All Numbers Disappeared in an Array 找到数组中消失的数字

题目描述

给定n个数字的数组，里面的值都是1-n，但是有的出现了两遍，因此有的没有出现，求没有出现值这个数组中的值有哪些。

要求不能用额外的空间（除了返回列表之外），时间复杂度n

思路

因为不能用额外空间并且时间是O(n)，所以不能用排序或者hash

通过在对应位置的值去确定下一个位置，一直到遍历完。其实自己也没有很成熟的思想。

比如对于[4,3,2,7,8,2,3,1]:

A[0],4=>找到a[3],7=>a[6],3=>a[2]====注意有可能出现循环，行不通。

本来以为行不通，后来经过思考，可以行得通，只不过复杂度是O(k*n)，k是重复的数字的个数，也是缺少的数字的个数。思路是这样的A[0],4，并且把A[0]标记为-1=>a[3],7并把4放到a[3]=>a[6],3,把7放到a[6],=>a[2],2,把3放到a[2]=>a[1],3，把2放到a[3],===>想把3放到a[2]，只是a[2]已经=3，所以3是数组中重复的。一个循环结束，从A[0]又开始，找到!=-1,并且!=i+1的a[i]，把里面的值放到对应的位置上。一直到所有位置不是-1就是i+1结束。位置是-1的，对应空缺数值i+1。

代码

    public static List<Integer> findDisappearedNumbers(int[] nums) {

        List<Integer> result=new ArrayList<>();

        boolean isEnding=false;//用isEnding检查是否所有位置不是-1就是i+1

        boolean isExist=false;//是否从上一个位置取出了数字

        int i=0;//代表找到的位置

        while(!isEnding){

            isEnding=true;

            i=0;

            while(i<nums.length){

                if((nums[i]!=i+1)&&(nums[i]!=-1)){//没有重复，可以放进去

                    isEnding=false;

                    int tmp=nums[i];

                    if(isExist){//如果有可以放进去的值，就先取出来再放进去

                        nums[i]=i+1;

                    }else{//否则，只能取出来，并把-1放进去

                        nums[i]=-1;

                    }

                    i=tmp-1;

                    isExist=true;

                }else{//如果相等，那么就重复了不需要放进去，直接往前面去;碰到了-1，如果需要放进去，就先放进去，再往后面去

                	if(isExist&&nums[i]==-1){

                		nums[i]=i+1;

                	}

                    i++;

                    isExist=false;

                }

            }

        }

        for(i=0;i<nums.length;i++){

            if(nums[i]==-1){

                result.add(i+1);

            }

        }

        return result;

}

分析

巴特西

[LeetCode] 448. Find All Numbers Disappeared in an Array 找到数组中消失的数字

题目描述

思路

代码

分析

最新文章

热门文章