九日集训第五天

题目 https://articles.zsxq.com/id_hwtn8ivz2ob4.html

1. 排序数组

本人熟悉java， C 语言不太熟练仅能看懂代码。所以解题答案，以Java为主，希望以后可以熟练使用C 语言写题解。

解题思路

1. 设计比较函数cmp
2. 调用比较函数qsort

C 语言

int cmp(const void *a,const void *b){      //(1)
    return (*(int *)a) - (*(int *)b);
}
int* sortArray(int* nums, int numsSize, int* returnSize){
    int * ret = (int *) malloc(sizeof(int) * numsSize);
    int i;
    for(i = 0; i < numsSize; ++i){
        ret[i] = nums[i];
    }

    qsort(ret,numsSize,sizeof(int),cmp);    //(2)
    *returnSize = numsSize;

    return ret;
}

java 写法

偷个懒

class Solution {
    public int[] sortArray(int[] nums) {   
        return  Arrays.sort( nums );
    }
}

2. 多数元素

解题思路

1. 使用map 集合key存放数组，value 存放 元素出现次数，
2. 循环遍历出，出现次数最多的map 元素，
3. 返回对应key 的元素。

java

class Solution {
    public int majorityElement(int[] nums) {
       HashMap<Integer, Integer> maps = new HashMap<>();

       for (int num: nums){                                 //(1)
           maps.put( num, maps.getOrDefault( num,0 )+1);
       }

       Map.Entry<Integer, Integer> majorityEntry = null;
       for (Map.Entry<Integer, Integer> entry : maps.entrySet()){  //(2)
           if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
              majorityEntry = entry;
           }           
        }
       return majorityEntry.getKey();                          //(3)
    }
}

3.存在重复元素

解题思路

1. 判断数组长度小于等于1，直接不满足条返回
2. 使用Set 集合特性存储数组元素，在存储之前判断是否存在该元素，如果不存在则加入set 集合。
3. 如果存在，则满足存在重复元素的条件，直接返回true.
4. 当循环遍历完，依然找不到重复元素，则返回false.

java

 class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        if(nums.length<=1){
            return false;
        }
        for (int i = 0; i < nums.length; i++) {
            if(!set.contains(nums[i])){
                set.add( nums[i] );
            }else {
                return true;
            }
        }
        return false;
    }
}

4.最大间距

解题思路

1. 数组元素小于等于1，没有间距直接返回0
2. 对数组进行排序
3. 遍历输出相邻元素最大间隔

java

class Solution {
    public int maximumGap(int[] nums) {
        if(nums.length <=1){
            return 0;
        }

        Arrays.sort( nums );
        int ans = 0;
        for (int i = 0; i< nums.length-1; i++){
            ans = Math.max( ans,nums[i+1] - nums[i]  );
        }
        return ans;
    }
}

5.按照奇偶数排序

解题思路

1. 使用双指针，创建一个等长的空数组。

2. 使用循环遍历，采用双指针，

   1. 当数组元素为偶数时，存入前面，
   2. 当数组元素为奇数时存入后面。

3. 循环结束，排序完成。

java

class Solution {
        public int[] sortArrayByParity(int[] nums) {
            int n = nums.length, start = 0,end =1;
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                if( nums[i]%2 == 0){
                    res[start++] = nums[i];
                }else{
                    res[n-end++] =nums[i];                    
                }
            }
            return res;
        }
}

6 最小时间差

解题思路

1. 开辟空间，定义时间差变量ans 最大值为24*60 =1140
2. 代码中（1） 执行for 循环将时间点转换位代表分钟数的int 类型。
3. (2) 对ret[i] 数组进行排序
4. (3) 再次for 循环求出每个时间点的时间差。
5. （4） 求出最小时间点和最大时间点的真实时间差。

C语言

int cmp(const void *a,const void *b){
    return *(int *)a -*(int *)b;
}

int min(int a,int b){
    return a < b? a : b;
}

int findMinDifference(char ** timePoints, int timePointsSize){
    int *ret = (int *)malloc(sizeof(int)*timePointsSize);
    int i,ans = 1440;
    int a,b;
    for( i = 0; i< timePointsSize; ++i){            //(1)
        sscanf(timePoints[i], "%d:%d",&a,&b);
        ret[i] = a*60 + b;
    }

    qsort(ret,timePointsSize,sizeof(int),cmp);      //(2)
    
    for(i = 1; i< timePointsSize; ++i){             //(3)
        ans = min(ans,ret[i] -ret[i-1]);
    }
  
    ans = min(ans,ret[0] - ret[timePointsSize-1] + 1440);

    return ans;
}