【算法】Java笔试算法题中数组的经典题总结的解题方法

布满荆棘的人生 2021-07-24 20:53 252阅读 0赞

# 前言 #

> 最近参加了一些公司的笔试和面试,自认为将java的编程能力提升(这里专指的是关于Java的知识,比如java的基础知识,框架等)就可以成功拿到offer，然后我发现`是我异想天开`了,对于我个人而言,java方面的知识,掌握的程度还行,现在最最`欠缺的是对于算法和数据结构的编程题`,也许是因为自己很久没有做数据结构和算法方面的编程题,对于这方面有点生疏。

因此决定在接下来的时间内，对于一些重要的算法和数据结构的思想和做题思路做一个总结。`希望自己早日能到满意的offer`

`算法和数据结构的编程题已经变成了拿大厂offer的敲门砖`

# 数组 #

## 第一题:两数之和 ##

![image-20200923203724588][]

> 做算法题,`如果刚开始没有思路,先想一些比较low的作法,只要是能完成题目的要求也是可以的`,然后再想办法将算法优化.往往第一个思路会给后面算法的优化提供很好的思路.

当我拿到这道题目的时候,没思路,那么就`暴力法`

针对该题的暴力法:就是遍历整个数组,将数组中的每个数都与数组中其他的数配对,寻找是否有相加的结果是target的组合,如果有,那么就输出他们的下标值。

class Solution { 
        public int[] twoSum(int[] nums, int target) { 
            //1.比较容易想到的方法就是使用暴力法,穷举出所有的数的组合
            //缺点也很明显,就是时间复杂度比较高是n^2
            //时间复杂度比较低的算法是使用哈希表的方式
            for (int i = 0; i < nums.length; i++) { 
                for (int j = i + 1; j < nums.length ; j++) { 
                    if (nums[i] == target - nums[j]){ 
                        return new int[]{ i,j};
                    }
                }
            }
            throw new IllegalArgumentException("No two sum solution");
        }
    }

**想要提升算法的能力,一定要在做题之前和做题之后分析自己算法的时间复杂度(一般情况下,不太考虑空间复杂度)**

> 我们使用了暴力法,在遍历数组中每个元素和别的元素进行组合的时候使用了双层的for循环,因此时间复杂度是n^2,这个时间复杂度算是比较高阶的时间复杂度了,是比较low的算法。

要解决这个两数之和的算法，我们还可以使用哈希表，但是我希望做一个系统方法记录，因此哈希表的算法在之后整理了哈希表的算法总结之后再回过头来讲解这道题的解法。

## 第二题：删除排序数组中重复的项 ##

![image-20200923231321501][]

> 拿到这个题先分析:
> 
> 1.  给出的条件:排序好的数组
> 2.  要求:`原地`删除重复的元素
> 3.  返回移除元素数组之后的数组的长度

> 原地删除,不能使用额外的空间,要删除重复的元素,首先要获得数组中的元素,那一定就要遍历数组,提供的是排序,因此只需要比较互相相邻的多个元素就可以确定是否是重复的元素

class Solution { 
        public int removeDuplicates(int[] nums) { 
            //1.要求原地删除数组中重复的元素
            //首先的想法是如何删除数组中重复的元素---暴力法->遍历数组
            //原地删除,就是不使用额外的空间
            if (nums.length==0){ 
                return 0;
            }
            int i = 0;
            for (int j = 1; j < nums.length; j++) { 
                if (nums[j] != nums[i]){ 
                    i++;
                    nums[i] = nums[j];
                }
            }
            return i + 1;
    
        }
    }

![image-20200923235250767][]

时间复杂度分析:使用了双指针的方式,在数组的原地重新赋值,实现了对重复元素的删除,时间复杂度:只使用了一层的for循环来遍历数组,因此时间复杂度是O(N).

## 移除元素 ##

![image-20200923235918768][]

这个题和删除排序数组中的重复项非常的相似,可以同样使用数组+双指针的方式解答

class Solution { 
        public int removeElement(int[] nums, int val) { 
            int i = 0;
            for (int j = 0; j < nums.length; j++) { 
                if (nums[j] != val){ 
                    nums[i] =nums[j];
                    i++;
                }
            }
            return i;
    
        }
    }

时间复杂度分析:单层for循环,O(n)的时间复杂度

[image-20200923203724588]: /images/20210724/09279204ba364531bf2fe2641a1ed270.png
[image-20200923231321501]: /images/20210724/43a9969e30af4e0a9f3cdaccd83cff42.png
[image-20200923235250767]: /images/20210724/96c36fd3c6b84919893ef9cfdccdcc48.png
[image-20200923235918768]: /images/20210724/4151902553d64f348e189e21f7075bba.png