剑指offer_数组中的重复数字

浅浅的花香味﹌ 2022-06-09 11:23 135阅读 0赞

/*
    在一个长度为n的数组里的所有数字都在0到n-1的范围内。 
    数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 
    例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
    
    直接思路：
    利用辅助数组，遍历原数组，每出现一个数字，将辅助数组中该数字作为下标的元素值加1，下标大于1的就是重复元素
    考虑不存在重复时如何处理
    
    */
    
    class  Duplicate
    {
    	public static boolean duplicate(int numbers[],int length,int [] duplication) {
    		if (numbers==null||length<=0)
    		{
    			return false;
    		}
    
    		int[] arrayTemp=new int[length];
    
    		for (int i=0; i<length; i++)
    		{
    			arrayTemp[numbers[i]]++;
    		}
    
    		duplication[0]=-1;
    		for (int i=0; i<length; i++)
    		{
    			if (arrayTemp[i]>1)
    			{
    				duplication[0]=i;
    				break;
    			}
    		}
    
    		if (duplication[0]==-1)
    		{
    			return false;
    		}
    
    		return true;
        }
    
    	//可以不用遍历整个数组，一边遍历一边判断是否重复，因为只要找到一个重复的就可以，不用全部处理
    	public static boolean duplicate2(int numbers[],int length,int [] duplication) {
    		if (numbers==null||length<=0)
    		{
    			return false;
    		}
    
    		int[] arrayTemp=new int[length];
    		duplication[0]=-1;
    
    		for (int i=0; i<length; i++)
    		{
    			if (arrayTemp[numbers[i]]==1)
    			{
    				duplication[0]=numbers[i];
    				break;
    			}
    			arrayTemp[numbers[i]]++;
    		}
    
    		if (duplication[0]==-1)
    		{
    			return false;
    		}
    
    		return true;
        }
    
    	//剑指offer：空间复杂度为O(1)
    	public static boolean duplicate3(int numbers[],int length,int [] duplication) {
    		    	if (numbers==null||length<=0)
    		{
    			return false;
    		}
    
    		duplication[0]=-1;
    
    		for (int i=0; i<length; i++)
    		{
    			//如果numbers[i]不在自己最终位置上，numbers[i]可能是重复数字
    			while (numbers[i]!=i)
    			{
    				//如果numbers[i]最终位置上的数字与numbers[i]相等，则numbers[i]为重复数字
    				if (numbers[i]==numbers[numbers[i]])
    				{
    					duplication[0]=numbers[i];
    					return true;
    				}else
    				//如果numbers[i]最终位置上的数字与numbers[i]不相等，将numbers[i]放到最终位置上
    				{
    					int temp=numbers[i];
    					numbers[i]=numbers[temp];
    					numbers[temp]=temp;
    				}
    			}
    			//如果numbers[i]在自己最终位置上则扫描下一个数字
    		}
    
    		if (duplication[0]==-1)
    		{
    			return false;
    		}
    
    		return true;
        }
    
    	public static void main(String[] args) 
    	{
    		int[] num={2,1,3,1,4};
    		int[] duplication=new int[1];
    		if(duplicate2(num,num.length,duplication))
    			System.out.println(duplication[0]);
    	}
    }