[数据结构与算法]【刷题日记】day1

时隔两个多月，不颓废了，题目刷起来！

1、数组序号转换

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 int cmp(int *a,int *b){
     return (*(int *)a)-(*(int *)b);
 }

 int binarySearch(int nums[],int target,int len){
     int right=len-1;
     int left=0;
     while(left<=right){
         int mid=(left+right)/2;
         if(nums[mid]==target){
             return mid;
         }else if(nums[mid]<target){
             left=mid+1;
         }else if(nums[mid]>target){
             right=mid-1;
         }
     }
     return -1;
 }

int* arrayRankTransform(int* arr, int arrSize, int* returnSize){
    int *ans=(int *)malloc(sizeof(int)*arrSize);
    int *que=(int *)malloc(sizeof(int)*arrSize);
    for(int i=0;i<arrSize;++i){
        ans[i]=arr[i];
        que[i]=1;
    }
    qsort(ans,arrSize,sizeof(ans[0] ),cmp);
    int cnt=1;
    for(int j=1;j<arrSize;++j){
        if(ans[j]==ans[j-1]){
            que[j]=cnt;
        }else{
            que[j]=++cnt;
        }
    }
    for(int k=0;k<arrSize;++k){
        arr[k]=que[binarySearch(ans,arr[k],arrSize)];
    }
    *returnSize=arrSize;
    return arr;
}

这道题有看题解，自己的思路差了一点，在用序号输出的那一步总是出错，看了题解后才意识到二分查找，因为平时很少用二分，故而不是很熟悉。

记录一下二分查找：

 int binarySearch(int nums[],int target,int len){
     int right=len-1;
     int left=0;
     while(left<=right){
         int mid=(left+right)/2;
         if(nums[mid]==target){
             return mid;
         }else if(nums[mid]<target){
             left=mid+1;
         }else if(nums[mid]>target){
             right=mid-1;
         }
     }
     return -1;
 }
 

2、`数组中出现次数超过一半的数字

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int>hash;
        for(int k:nums){
            hash[k]++;
        }
        int num=0;
        int len=nums.size()/2;
        for(int i=0;i<nums.size();i++){
            if(hash[nums[i]]>len){
                num=nums[i];
            }
        }
        return num;
    }
};

3、出现频率最早的k个数字

学习度不够，hash表C++用的熟，在c中居然都不会用了。偏偏思路用C会写，emm。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 int cmp(int *a,int *b){
     return (*(int *)a)-(*(int *)b);
 }

struct hash{
    int val;
    int cnt;
};

int cmpHash(int *a,int *b){
    struct hash *node1=(struct hash*)a;
    struct hash *node2=(struct hash*)b;
    return node2->cnt-node1->cnt;
}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
    int *ans;
    struct hash *nums_in;
    int target_val;
    int target_idx;
    int target_cnt;

    qsort(nums,numsSize,sizeof(int),cmp);

    nums_in=(struct hash*)malloc(sizeof(struct hash)*numsSize);

    target_val=nums[0];
    target_idx=0;
    nums_in[0].val=nums[0];
    nums_in[0].cnt=0;

    for(int i=0;i<numsSize;++i){
        if(target_val!=nums[i]){
            target_idx++;
            nums_in[target_idx].val=nums[i];
            nums_in[target_idx].cnt=1;
            target_val=nums[i];
        }else{
            nums_in[target_idx].cnt++;
        }
    }

    qsort(nums_in,target_idx+1,sizeof(struct hash),cmpHash);

    *returnSize=k;
    ans=(int *)malloc(sizeof(int)*k);

    for(int i=0;i<k;++i){
        ans[i]=nums_in[i].val;
    }
    return ans;
}