Leetcode 4

Array Easy

1. 268. Missing Number

　　先对数组求和，用 0 ~ n本该有的和减去当前sum得到缺失的数字。

1 class Solution {
2     public int missingNumber(int[] nums) {
3         int sum = 0;
4         for ( int i = 0 ; i < nums.length ; i++){
5             sum += nums[i];
6         }   
7         return ((nums.length) * (nums.length + 1 )/2) - sum;
8     }
9 }

2. 169. Majority Element

　　利用HashMap键值对记录次数，并用最大次数大于n/2来判定满足条件

 1 class Solution {
 2     public int majorityElement(int[] nums) {
 3         int len = nums.length;
 4         if( len == 1)
 5             return nums[0];
 6         
 7         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
 8         for( int i = 0; i < nums.length ; i++){
 9             if(!map.containsKey(nums[i])){
10                 map.put(nums[i],1);
11             }else{
12                 int times = map.get(nums[i]);
13                 map.put(nums[i], times+1);
14                 if(times+1 > len/2)
15                     return nums[i];
16             }
17         }
18         return 0;
19     }
20 }

3. 189. Rotate Array

　　先把整个数组翻转一下, 再把前k个数字翻转一下，再把后n - k个数字翻转一下。翻转的逻辑可以梳理一下

 1 class Solution {
 2     public void rotate(int[] nums, int k) {
 3         int len = nums.length;
 4         k = k % len;
 5         reverse(nums, 0, len-1);
 6         reverse(nums, 0, k -1);
 7         reverse(nums, k, len-1);
 8     }
 9     
10     public static void reverse(int[] nums, int l, int r){
11         while( l < r){
12             int temp = nums[l];
13             nums[l] = nums[r];
14             nums[r] = temp;
15             l++;
16             r--;
17         }
18     }
19 }