leetcode一些题的想法

167. Two Sum II - Input array is sorted

这道题是给定一个数组和一个数字a，再数组中查找两个数其之和等于a，两个数不会取同一个数，数必定有解，数组有序。

暴力的是两层for循环，复杂度n方，然后改为了折半查找，平均复杂度是nlogn。

比较优化的是利用两个数之和的数学关系，如果这两个数小于a，必定一个数取值小了，角标增改++，如果大于a，一个数的取值大了，角标--。我列出代码（代码不是我写的，嘻嘻）

   int i = 0, j = numbers.length - 1;
        
        while(i < j) {
            int tmp = numbers[i] + numbers[j];
            
            if(tmp < target)
                i++;
            else if(tmp > target)
                j--;
            else
                break;
        }
        
        return new int[] {i + 1, j + 1};

这是我根据上面的思路改的。

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length-1;
        int a = numbers[i]+numbers[j];
        while(a!=target){
            if(a>target)j--;
            else i++;
            a = numbers[i]+numbers[j];
        }
        
        int[]a1={i+1,j+1};
        return a1;
    }   
}

169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

题意：给你一个数组，让你找打一个数量超过n/2的数，假定数组非空，且这个数字必定存在

解1：这个数组排序，统计每种数字出现的次数

解2：排序，通过题意可知这个被查找的数字必定出现在nums[n/2]上，直接返回这个值就可以了

解3：（看到别的答案看到的）不需要排序，由题意知道这个数字必定会比别的数字多出至少一个，利用这个性质，在数组中删掉两个不同的数字（不是真正以上的删除），不停删除，知道剩下的数只有一个（elem）。这个数字便是我们要查找的。下面是解3的代码。

  	  int elem = 0;//要查找的那个数字
          int count = 0;//用来判断
          
          for(int i = 0; i < num.size(); i++)  {
              
             if(count == 0)  {
                 elem = num[i];
                 count = 1;
             }
             else    {
                 if(elem == num[i])
                     count++;
                 else
                     count--;
             }
             
         }
         return elem;