Leetcode 4

Array Easy

1. 268. Missing Number

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

 class Solution {

     public int missingNumber(int[] nums) {

         int sum = 0;

         for ( int i = 0 ; i < nums.length ; i++){

             sum += nums[i];

         }

         return ((nums.length) * (nums.length + 1 )/2) - sum;

     }

 }

2. 169. Majority Element

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

 class Solution {

     public int majorityElement(int[] nums) {

         int len = nums.length;

         if( len == 1)

             return nums[0];

         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

         for( int i = 0; i < nums.length ; i++){

             if(!map.containsKey(nums[i])){

                 map.put(nums[i],1);

             }else{

                 int times = map.get(nums[i]);

                 map.put(nums[i], times+1);

                 if(times+1 > len/2)

                     return nums[i];

             }

         }

         return 0;

     }

 }

3. 189. Rotate Array

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

 class Solution {

     public void rotate(int[] nums, int k) {

         int len = nums.length;

         k = k % len;

         reverse(nums, 0, len-1);

         reverse(nums, 0, k -1);

         reverse(nums, k, len-1);

     }

     public static void reverse(int[] nums, int l, int r){

         while( l < r){

             int temp = nums[l];

             nums[l] = nums[r];

             nums[r] = temp;

             l++;

             r--;

         }

     }

 }

巴特西

Leetcode 4

最新文章

热门文章