欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

找出数组中重复的数和二维数组中的查找

程序员文章站 2022-05-12 10:41:37
...

一.找出数组中重复的数

在长度为n的数组nums里面的所有数字都在0~n-1的范围内,数组中某些数字是重复的,但不知道是哪几个,也不知道重复了几次,请找出数组中任意重复的数字

解法:
1.暴力解法:循环遍历逐个比较,我们可以利用两次循环找出一对相等的数返回

for(int j=0;i<n-1;j++){
   for(int i=j+1;i<n;i++)
   {
    if(nums[j]==nums[i])
         return nums[j];
   }
}

这种方法的好处在于不必改变数组结构,坏处在于时间复杂度高。

2.排序相邻判断法:我们可以先对数组进行排序,然后判断第一对相邻且相等的数即可

Arrays.sort(nums);
for(int j=0;j<n-1;j++){
   if(nums[j]==nums[j+1])
      return nums[j];
}

这种方法的坏处是改变了原有数组的结构,好处是相比暴力解法降低了时间复杂度。

3.哈希法:我们可以创建一个哈希集(HashSet)依次向哈希集中添加元素,第一个添加失败的就是重复的数

Set set=new HashSet();
int end=-1;
for(num:nums){
   if(!set.add(num))
   {end=num;
    break;
    }
   return end;
}

这种方法是比较好的,用空间换取时间,时间复杂度很低。

4.特殊解法:原地置换,根据题目我们可知,如果没有重复的数字,那么正常排序后,数字i应该在下标为i的位置上,所以思路是重头扫描数组,遇到下标为i的数字如果不是i,我们就拿它与下标为该数字
的数字交换,在交换的过程中,如果有重复的数字发生,返回之

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

此方法很巧妙。

二.二维数组中的查找

在一个n*m的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序,请完成一个函数,输入这样一个二维数组nums[][]和整数,判断数组中是否存在该数?

解法:
1.暴力法:我们可以遍历完整个数组进行判断

int rows=nums.length;
int columns=nums[0].length;
if(nums==null||rows==0||columns==0) return false;
               
for(int i=0;i<rows;i++){
   for(int j=0;j<colums;j++){
      if(nums[i][j]==target)
          return true;
  }
}
return false;

此方法的时间复杂度为n*m,比较高

2.右上角开始的判断法:我们可以结合题中二维数组的性质,选用从右上角开始的判断排除
若右上角的数大于目标数,则左移一位
若右上角的数小于目标数,则下移一位,依次类推,直到找到目标数。

int rows=nums.length;
int columns=nums[0].length;
if(nums==null||rows==0||columns==0) return false;
int row=0;
int column=columns-1;
while(row<rows&&colum>=0){

   int num=nums[row][column];
   
   if(num==target)  return true;
   
   else if(num>target)  column--;
   
   else row++;
}
return false;

此方法的时间复杂度仅为n+m,相比暴力解题更加优秀。

相关标签: 算法专题学习