[算法]存在重复元素

上一篇 / 下一篇  2019-05-30 11:33:48 / 天气: 阴雨 / 心情: 平静 / 个人分类:算法

最近在准备面试,学习到不少算法题目。希望总结下来,在以后的工作中有所帮助,提升自己的能力。

问题一:
给定一个整数数组,判断是否存在重复元素。如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。

示例 1:
输入: [1,2,3,1]
输出: true

示例 2:
输入: [1,2,3,4]
输出: false

示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

思路1:
以我的初级编程水平,第一个思路是用双层for循环,不考虑空间复杂度和时间复杂度。以JAVA代码为例:
class Solution {
    public boolean containsDuplicate(int[] nums) {
        int index1 = 0;
        int index2 = 0;
        int len = nums.length;
        System.out.println("len is: " + len); //for debugging
       
        int target = 0;
        int next = 0;
       
        for(index1 = 0; index1<len; index1++){
            for(index2 = index1+1; index2<len; index2++){
                target = nums[index1];
                System.out.println("previous is:" + target);//for debugging
                next = nums[index2];
                System.out.println("next is:" + next);//for debugging
                if(target==next)
                    return true;
                else
                    continue;
            }
        }
        return false;
    }
}

现在增加题目要求,“不得嵌套循环,不得使用递归”。如此,上述JAVA代码就不符合要求了,并且在leetcode上提交执行以后显示“超出时间限制”。

思路2:
若将题目变为:
给定一个整数数组,判断是否存在重复元素。如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。
不得嵌套循环,且需要保证额外的空间复杂度为O(1),则需要考虑使用“堆”排序。//TBD


TAG:

 

评分:0

我来说两句

日历

« 2024-03-28  
     12
3456789
10111213141516
17181920212223
24252627282930
31      

数据统计

  • 访问量: 12793
  • 日志数: 32
  • 图片数: 1
  • 建立时间: 2019-01-22
  • 更新时间: 2019-08-08

RSS订阅

Open Toolbar