leetcode528. 按权重随机选择

Dear 丶 2022-09-09 11:52 133阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_13_color_FFFFFF_t_70_g_se_x_16]  
思路

1.  权重模拟  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_20_color_FFFFFF_t_70_g_se_x_16]

typedef struct { 
        int max;
        int count;
        int w[10001];
    
    } Solution;
    
    
    Solution* solutionCreate(int* w, int wSize) { 
        Solution* t = (Solution*)malloc(sizeof(Solution));
        t->max =0;
        t->count = wSize;
        int i;
        for(i=0;i<wSize;i++){ 
            t->w[i] = w[i];
            t->max += w[i];
        }
        return t;
    
    }
    
    int solutionPickIndex(Solution* obj) { 
        int t =rand()%(obj->max)+1;
        int i;
        for(i=0;i<obj->count;i++){ 
            if(t>obj->w[i])
                t-=obj->w[i];//相减，以长度关系模拟区间
            else
                break;
        }
        return  i;
    }
    
    void solutionFree(Solution* obj) { 
        free(obj);
    }
    
    /** * Your Solution struct will be instantiated and called as such: * Solution* obj = solutionCreate(w, wSize); * int param_1 = solutionPickIndex(obj); * solutionFree(obj); */

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/4d8f893ce7ca4a1d9834c3e2bfabf670.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/8cf4b828402548f3aaaec1515af67fc6.png