两数之和

题目：给出一个整数数组，请在数组中找出两个加起来等于目标值的数，
你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2.。注意：下标是从1开始的
假设给出的数组中只存在唯一解
例如：
给出的数组为 {20, 70, 110, 150},目标值为90
输出 index1=1, index2=2

思路：① 我们需要让数组中的每个元素进行相加。从而进行判断是否等于目标值。
② 可以使用两个for循环，从而达到每个元素两两相加的目的。

示例： ① 存在数组 {3,2,4} 目标值为 6。
先让第一个数和其他数相加，如果没找到，就让第二个数和第二个数之后的数相加。
找到了，所以index1 = 2， index2 = 3.

  1. ② 存在数组{0,4,4,0} 目标值为0<br />同理，让第一个数与剩下的数相加：<br />0 + 4  != 0<br />0 + 4  != 0<br />0 + 0  == 0<br />所以返回index1 = 1，index2 = 4

③ 存在数组{1,5,6,7,11}，目标值为:13
同理，让第一个数与剩下的数相加：
1 + 5 != 13
1 + 6 != 13
1 + 7 != 13
1 + 11 != 13
于是，让第二个数与剩下的数相加
5 + 6 != 13
5 + 7 != 13
5 + 11 != 13
再让第三个数与剩下的数相加：
6 + 7 == 13
于是，返回index1 = 3 index2 = 4。

代码实现：

  1.    public int[] twoSum (int[] numbers, int target) {
  2.         int index1 = 0;
  3.         int index2 = 0;
  4.         int[] answer = null;
  5.         // 两个for循环
  6.         for(int i = 0; i<numbers.length; i++){
  7.             for(int j = i+1; j<numbers.length;j++){
  8.                 if(numbers[i]+numbers[j] == target){
  9.                     index1 = i;
  10.                     index2 = j;
  11.                     break;
  12.                 }
  13.             }
  14.         }
  16.         if(index1==0 && index2==0){
  17.             return null;
  18.         }else{
  19.            answer = new int[]{index1+1,index2+1};
  20.             return answer;
  21.         }
  22.     }

数组中出现超过一半的数字

题目：
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

示例：
{5,5,7,6,5,3,5,5,5,1}，该数组长度为10
数字5出现了6次，超过数组长度的一般，因此输出5。

思路一：
① 定义一个tag表示数组长度的一半
② 使用双层for循环遍历数组，给定一个count，用于记录每一个数组出现的次数。
③ 定义一个num，用于记录每一个数字。每记录一个数字的出现次数后，用count和tag比较，若比tag，则输出该数字。
④ 注意在每次比较完count后，要将count重新置为0。
时间复杂度为：O（n2）
空间复杂度为：O (1)

  1.  public int MoreThanHalfNum_Solution(int [] array) {
  2.         int length = array.length;
  3.         // 记录数组长度的一半
  4.         int tag = length>>1;
  6.         int count = 0; //记录某一个重复数字出现的次数
  7.         int num = 0;
  8.         // 遍历数组
  9.         for(int i = 0;i<length;i++){
  10.             count = 0;
  11.             num = array[i];
  12.             for(int j = 0;j<length;j++){
  13.                 if(num==array[j]){
  14.                     count++;
  15.                 }
  16.             }
  17.             if(count > tag){
  18.                return num;
  19.             }
  20.         }
  21.         return 0;
  22.     }

思路二：
① 使用HashMap，保存一个数字出现的次数
② 当数组只有一个元素时，直接返回这个元素
③ 当数组为空时，返回0.
④ 数组不为空，先判断map中是否存在该key（key就是数组中的一个元素），若存在，获取原key的val，记作：get(key)，再把该key存入map，其新值为 get(key)+1。然后判断其val是否超过了数组长度的一半，若超过，则返回当前key。
若不存在该key，则把该key添加到map中。
代码实现：其时间复杂度为O(n)，空间复杂度为O(n)。

  1.   public int MoreThanHalfNum_Solution(int [] array) {
  2.           int tag = array.length>>1;
  3.         HashMap<Integer,Integer> map = new HashMap<>();
  4.         if(array==null || array.length<1){
  5.             return 0;
  6.         }
  8.         if(array.length==1){
  9.             return array[0];
  10.         }
  12.         for(int i : array){
  13.             if(map.containsKey(i)){
  14.                 // 这里 +1是为了防止，{1,2,1}这种情况出现，当第二个1出现在最后一个元素时
  15.                 // 如果不 +1， 则返回的结果是0。
  16.                 if(map.get(i)+1>tag){
  17.                     return i;
  18.                 }
  19.                 map.put(i,map.get(i)+1);
  20.             }else{
  21.                 map.put(i,1);
  22.             }
  23.         }
  24.         return 0;
  25.     }

合并两个有序的数组

题目：
给出两个有序的整数数组A和B，请将数组B合并到数组A中，变成一个有序的数组。
注意：
可以假设A数组有足够多的空间存放B数组的元素，A和B中初始元素的数目为m和n。

示例： 数组A：{1,3,5,7,9}
数组B： {2,4,6,8,10}
合并后的数组： {1,2,3,4,5,6,7,8,9,10}

思路一 ：
① 使用两个指针记作：p1，p2。p1指向A数组的第一个，p2指向B数组的第一个。
② 定义一个新的数组，记作array。用于保存有序的值。
③ 使用循环，比较A数组中的元素和B数组中的元素的大小：
如果p1指向的数大于p2指向的数，则把p2所指的数放入array中，然后让p2++
反之，让p1所指的数放入array中，p1++。
④ 放入新数组array中的位置，应该是 p1+p2 -1。 或者单独定义一个变量tmp也行。
⑤ 要注意：如果p1==m 或 p2==n，则说明此时 数组A 或数组B已经没有元素了
若数组A中没有元素了，数组B中还有元素，则直接将数组B中剩余的元素，即p2及p2位置之后
的元素全部放到array中。反之亦然。
⑥ 最后，将新数组arrry中的值，拷贝到A数组中。
代码实现：

  1. public static void merge(int A[], int m, int B[], int n) {
  2.         int p1 = 0;
  3.         int p2 = 0;
  4.         int cur = 0;
  5.         int array[] = new int[m+n];
  6.         while(p1 !=m || p2!=n){
  7.             if(p1 == m){
  8.                 cur =B[p2++];
  9.             }else if(p2 == n){
  10.                 cur = A[p1++];
  11.             }else if(A[p1]>=B[p2]){
  12.                 cur = B[p2++];
  13.             }else{
  14.                 cur = A[p1++];
  15.             }
  16.             array[p1+p2-1] = cur;
  17.         }
  19.         System.arraycopy(array,0,A,0,array.length);
  20.     }

思路二：
① 思路一中 我们使用了多余的空间，即新创建的array[]，如果我们不使用新的array，直接在数组A中插入，则在插入的过程中，势必会覆盖数组A中，原有的值。
② 为了避免，会覆盖原有的值。题目已经告知，数组A的长度可以看做是 m+n
数组A：{8,9}
数组B：{1,2,3,5,10,11}
可以把数组A看成： {8,9,0,0,0,0}

数组A：{5,6,7,9,10}
数组B：{1}
就可以把数组A看成：{5,6,7,9,10,0}

③ 我们同时需要使用双指针，但是这次我们不从前面开始比较，我们让p1，p2分别从A、B的最后一个元素开始比较。
④ 如果A[p1] >=B[p2] 则把B[p2]放在A中最后一个元素位置，此时让p2—，反之亦然。

代码实现：

  1.  public static void merge(int A[], int m, int B[], int n) {
  2.      // p1指向A数组最后一个元素
  3.          int p1 = m-1;
  4.      // p2指向B数组最后一个元素
  5.          int p2 = n-1;
  6.      // 记录A、B两数组中的较大值
  7.          int cur = 0; 
  8.      // 用于标记cur存放的位置。
  9.          int last = m+n-1;
  10.      // 通过循环进行比较，循环终止的条件是，p1==-1 并且 p2==-1，若两个都为-1，则说明两数组中的元素都已经遍历完了。
  11.         while(p1!=-1||p2!=-1){
  12.             if(p1==-1){
  13.                 cur = B[p2--];
  14.             }else if(p2==-1){
  15.                 cur = A[p1--];
  16.             }else if(A[p1]>=B[p2]){
  17.                 cur = A[p1--];
  18.             }else{
  19.                 cur = B[p2--];
  20.             }
  21.             A[last--] = cur;
  22.         }
  23.     }

斐波那契数列

题目：
从数组的第二项开始，每一项为前两项的和，求第n项的值。
斐波那契数列： 0 1 1 2 3 5 8 13 21 …
数组第0项为0，第一项为1。

思路一：
递归：第n项的值为第n-1项+第n-2项的和。时间复杂度为： O(2^n)

代码实现：

  1. public int Fibonacci(int n) {
  2.         if(n==0) return 0;
  3.         if(n==1) return 1;
  4.         return Fibonacci(n-1) + Fibonacci(n-2);
  5. }

思路二： 使用循环
从第二项开始，每一项是前两项的和，我们可以使用两个变量 a，b分别表示前n-1项和前n-2项的和。

代码实现：

  1.     public int Fibonacci(int n) {
  2.         if(n == 0) return 0;
  3.         if(n == 1) return 1;
  4.         int a = 0; int b = 1; int c = 0; 
  5.         for(int i = 2; i<=n;i++){
  6.             c = a+b;
  7.             a = b;
  8.             b = c;
  9.          }
  10.         return c;
  11.     }

寻找峰值

题目：
山峰元素是指其值大于或等于左右相邻值得元素，给定一个输入数组nums，任意两个相邻元素值不相等，数组可能包含多个山峰。找到索引最大的哪个山峰元素并返回其索引。

示例：
数组[2,4,1,2,7,8,4]
返回索引：5

思路：
其实就是找值，只不过是找索引最大的并且比左右两边元素都大的值。

代码实现：
从前往后找：

  1.     public int solve (int[] a) {
  2.         int index = 0;
  3.         for(int i = 1; i<a.length;i++){
  4.             if(a[i-1]<a[i]){
  5.                 index = i;
  6.             }
  7.         }
  8.         return index;
  9.     }
  1. <br />也可以从后往前找：
  1. public int solve(int[] a){
  2.     for(int i = a.length-1; i>0; i--){
  3.         if(a[i]>=a[i-1]){
  4.             return i;
  5.         }
  6.     }
  7.     return -1;
  8. }

寻找数组中第一大和第二大的数

题目：
给定一个数组，输出数组中第一大和第二大的数。
示例：
给定数组arr： {9,6,10,25,30,1,19,80,16}
输出： 30 80。
思路：
① 定义两个变量用来保存 第一大和第二大的数。分别记作：max1、max2
② 我们可以让数组的第一个和第二个元素充当第一大和第二大元素
③ 往后遍历数组，如果arr[i] > max1 说明，i位置上的数大于max1(即第一大的数)。于是交换数据：
max1变为 arr[i]
max2变为原来的max1
如果arr[i] > max2 但 arr[i] < max1
说明，i位置上的数 大于第二大的数，却小于第一大的数
于是，我们只需要将max2变为arr[i]即可。
代码实现：

  1.  public static void print_twoMax(int[] ar){
  2.         int max1= (ar[0] > ar[1] ?ar[0]:ar[1]); // max1指第一大的数
  3.         int max2 =(ar[0] > ar[1] ?ar[1]:ar[0]); // max2指第二大的数
  4.         for (int i = 2; i < ar.length; i++) {
  5.             if (ar[i] > max1){ //如果该值大于第一大的数，我们就让第二大的数为原来的第一大的数
  6.                 max2 = max1;
  7.                 max1 = ar[i]; // 让原来的第一大的数变为i位置上的数
  8.             }else if(ar[i] > max2){ // 如果i位置上的数，不大于第一大的数，但是大于第二大的数
  9.                 max2 = ar[i]; // 就让原来第二大的数 变为 i位置上的数。
  10.             }
  11.         }
  12.     }

找出数组中第k小的值

题目：
给定一个数组，找出数组中第k小的值。
示例：
给定数组arr[] = {9,10,60,1,5,7,52,8,10};
k = 3 。即找出第3小的值
输出：7。
思路：
使用快速排序的思想。对数组进行划分。
第一次划分，得到分界点index。
如果k<=index，则说明第k小的值在index的左边，在左边继续划分。
如果k>index，则说明第k小的值在index的右边，在右边继续划分。
代码实现：

  1.  //划分
  2.     public static int partition(int[]ar,int left,int right){
  3.         int i = left;
  4.         int j = right;
  5.         int tag = ar[i];
  6.         while(i<j) {
  7.             while (i < j && ar[j] > tag) {
  8.                 j--;
  9.             }
  10.             if (i < j) ar[i] = ar[j];
  11.             while (i < j && ar[i] <= tag) {
  12.                 i++;
  13.             }
  14.             if (i < j) ar[j] = ar[i];
  15.         }
  16.         ar[i] = tag;
  17.         return i;
  18.     }
  20.     // 打印第k小的值。若k = 1，找的是第1小的值
  21.     public static int printK_Min(int[] ar,int k){
  22.         return printK(ar,0,ar.length-1,k);
  23.     }
  25.     private static int printK(int[] ar,int left,int right,int k){
  26.         if (left==right && k==1) return ar[left];
  27.         int index = partition(ar,left,right);
  28.         // pos指的是区域里的元素个数。
  29.         int pos = index - left + 1;
  30.         // 如果k小于这个元素个数，就说明 ，第k小的值一定存在于这个区域。
  31.         // 则在这个区域里找第k小的值
  32.         if (k<=pos) return printK(ar,left,index,k);
  33.         // 否则，就在后半段内区域找相对于这个区域来说第k小的值。
  34.         // k-pos是相对于后半段区域的绝对物理下标。
  35.         else return printK(ar,index+1,right,k-pos);
  36.     }

查找数组中第k大的值

题目：
给定一数组，找到数组中第k大的值。
示例：
给定数组arr[] = {145,81,213,423,14,234,45};
给定k=1
输出：423
思路：
和查找第k小的思路是一样的。
在第一次划分后，数组被我们分为两个区间，分别为 S左和S右
我们将S右中的元素个数记作：pos
首先，我们要判断 k 的值 是否超过了pos，如果超过了，就说明我们要找的值在S左中
如果没有超过，说明我们要找的值在S右中。
当我们找的值在S右时，k是几就是几。比如S右有4个元素，我们要查找k=3的值，即查找第3大的值，我们就在S右中继续找第3大的值。然后进行递归
当我们找的值在S左时，此时在S左这个区间，我们要查找的是 k-pos大的值。举个例子： 比如S左有4个元素，(注意这4个元素都是比我们第一次划分时用的目标值小的)当我们要查找第k=5大的值时，此时对应在S左这个区间里就应该是查找第 k-pos = 1 大的值。 然后进行递归

递归的终止条件是什么呢？
当我们的k==pos时。就到达了终止条件。

代码实现：

  1.  // 打印第k大的值
  2.     public static int printK_Max(int[]ar,int k){
  3.         return printkMax(ar,0,ar.length-1,k);
  4.     }
  5.     public static int printkMax(int ar[],int left,int right,int k){
  6.         int index = partition(ar,left,right);
  7.         int pos = right-index+1;
  8.         if (k==pos) return ar[pos];
  9.         if (k<=pos){
  10.             return printkMax(ar,index+1,right,k);
  11.         }else{
  12.             return printkMax(ar,left,index,k-pos);
  13.         }
  14.     }