数据结构算法题总汇

2021年10月25日数组练习

题目一：leetcode136.只出现一次的数字

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解思路：

1.拿到题目后第一反应是借助一个hash表来进行记录，但是空间复杂度会变为O（n），不符合题意。代码如下：

    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i])+1);
            }else{
                map.put(nums[i],1);
            }
        }
        for (Integer integer : map.keySet()) {
            int count = map.get(integer);
            if (count == 1){
                return integer;
            }
        }
        return -1;
    }

2.由于上一个解法使用hash导致空间复杂度提高，所以随后想到使用排序算法进行解题，但是使用快排的时间复杂度也达到了O（nlogn），所以放弃。

    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        int result = 0;
        if(nums.length == 1){
            return nums[0];
        }
        if (nums[0] != nums[1]){
            return nums[0];
        }
        for (int i = 1; i < nums.length; i++) {
            if (i== nums.length-1){
                if (nums[nums.length-1] != nums[nums.length-2]){
                    return nums[nums.length-1];
                }
                break;
            }
            if (nums[i] == nums[i+1] || nums[i-1] == nums[i]){
            }else{
                result = nums[i];
            }
        }
        return result;
    }

3.由于本人能力不足，想到这里就到头了，所以就默默的打开了题解，看到了一种异或操作来解这题，异或操作是属于相同为0，不同为1的运算，所以刚好用来解这题。

    public int singleNumber(int[] nums) {
         int result = nums[0];
         if (nums.length > 1){
             for (int i = 1; i < nums.length ; i++) {       
                 result = result ^ nums[i];       
             }
         }
         return result;
    }

4.还有一种解法，暴力解法，这个解法就不做解释了，就是将一个元素拿出来对数组剩下的元素做对比，时间复杂度达到了O（n平方）。

题目二：leetcode169:多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

1.看到题目首先想到使用hash表对元素出现的次数进行记录，但是题意空间复杂度的要求是O（1），不符合题意。

    public int singleNumber(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length ; i++) {
            if (map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i])+1);
            }else{
                map.put(nums[i],1);
            }
        }
        for (Integer integer:map.keySet()) {
            int count = map.get(integer);
            if (count > nums.length/2){
                return count;
            }
        }
        return -1;
    }

2.随后想到排序算法，由于众数的个数大于数组个数的一半，所以排完序之后的数组的中位数一定是众数。但是排序算法的时间复杂度是O（nlogn），故不符合题意。

    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

3.学习到了摩尔投票法求解众数问题，初始化一个候选人为nums[0],票数为1，每遇到一个相同的票数加一，遇到不相同的票数减一，最后候选人变量就是众数。

public static int majorityElement(int[] nums) {
        int num = nums[0];
        int count = 1;
 
        for (int i = 1; i < nums.length ; i++) {
            if (num == nums[i]){
                count++;
            }else{
                count--;
                if (count == 0){
                    num = nums[i];
                    count = 1;
                }
            }
        }
        return num;
    }

题目三：leetcode15:三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

1.首先想到的是暴力解法，三次for循环，但是三次for循环是不能解决去重问题的。

2.随后采用排序+双指针的问题解决此问题。排序后的数组是有序的，首先使用一个for循环确定一个数，然后使用双指针去寻找另外的两个数。然后去判断去重问题即可。 解决问题。

 public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length < 3){
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length ; i++) {
            //如果nums[i]大于0，后面的肯定都大于0，不可能相加等于0
            if (nums[i]>0) return result;
            int L = i + 1;
            int R = nums.length-1;
            if (i>0 && nums[i] == nums[i-1]) continue; //去重，对num[i]去重
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if (sum == 0){
                    result.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while(L<R && nums[L] == nums[L+1]) L++;//去重
                    while(L<R && nums[R] == nums[R-1]) R--;//去重
                    L++;
                    R--;
                }
                if(sum > 0) R--;
                if(sum < 0) L++;
            }
        }
        return result;
    }