鍔犳潈闅忔満閲囨牱绠楁硶璇﹁В锛氫汉鍙ｅ垎甯冧笌姒傜巼閫夋嫨

涓€銆侀棶棰樻弿杩?/h2>

鍦ㄨ澶氬疄闄呭簲鐢ㄤ腑锛屾垜浠渶瑕佹牴鎹笉鍚岀殑鏉冮噸鏉ラ殢鏈洪€夋嫨鍏冪礌銆傚吀鍨嬪満鏅寘鎷細

• 骞垮憡鎶曟斁锛氭寜鍑轰环鏉冮噸閫夋嫨灞曠ず鐨勫箍鍛?/li>
• 璐熻浇鍧囪　锛氭寜鏈嶅姟鍣ㄥ閲忓垎閰嶈姹?/li>
• 鎶藉绯荤粺锛氫笉鍚屽鍝佹湁涓嶅悓涓姒傜巼
• 鍩庡競浜哄彛閲囨牱锛氭寜浜哄彛姣斾緥闅忔満閫夋嫨鍩庡競

馃搶 绀轰緥闂锛?/strong>

缁欏畾鍩庡競鍙婂叾浜哄彛鏁版嵁锛氬寳浜?2100涓?銆佷笂娴?2400涓?銆佸箍宸?1500涓?銆傛瘡娆¤皟鐢ㄨ繑鍥炰竴涓煄甯傚悕锛岃繑鍥炴鐜囧簲姝ｆ瘮浜庡叾浜哄彛鍗犳瘮銆?/p>

鏈熸湜姒傜巼锛氬寳浜?35%銆佷笂娴?40%銆佸箍宸?25%

浜屻€佸墠缂€鍜?+ 浜屽垎鏌ユ壘鏂规

2.1 鏍稿績鎬濊矾

灏嗘潈閲嶈浆鎹负杩炵画鐨勫尯闂?/strong>锛岀劧鍚庣敓鎴愰殢鏈烘暟鍒ゆ柇钀藉叆鍝釜鍖洪棿锛?/p>

1. 璁＄畻鍓嶇紑鍜屾暟缁勶紝姣忎釜鍏冪礌浠ｈ〃涓€涓尯闂寸殑鍙宠竟鐣?/li>
2. 鐢熸垚 [0, 鎬绘潈閲? 鑼冨洿鍐呯殑闅忔満鏁?/li>
3. 浣跨敤浜屽垎鏌ユ壘瀹氫綅闅忔満鏁版墍灞炲尯闂?/li>

2.2 瀹屾暣瀹炵幇

class WeightedRandomSelector<T> {
    private items: T[];
    private prefixSum: number[];
    private totalWeight: number;
    
    constructor(itemsWithWeights: Array<{item: T, weight: number}>) {
        this.items = [];
        this.prefixSum = [];
        let cumulative = 0;
        
        for (const {item, weight} of itemsWithWeights) {
            this.items.push(item);
            cumulative += weight;
            this.prefixSum.push(cumulative);
        }
        
        this.totalWeight = cumulative;
    }
    
    select(): T {
        // 鐢熸垚 [0, totalWeight) 鑼冨洿鐨勯殢鏈烘暟
        const randomValue = Math.random() * this.totalWeight;
        
        // 浜屽垎鏌ユ壘绗竴涓ぇ浜?randomValue 鐨勫墠缂€鍜屼綅缃?
        let left = 0;
        let right = this.prefixSum.length - 1;
        
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (this.prefixSum[mid] <= randomValue) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return this.items[left];
    }
}

// 浣跨敤绀轰緥
const citySelector = new WeightedRandomSelector([
    { item: "鍖椾含", weight: 2100 },
    { item: "涓婃捣", weight: 2400 },
    { item: "骞垮窞", weight: 1500 }
]);

// 澶氭璋冪敤锛屾鐜囧垎甯冪鍚堜汉鍙ｆ瘮渚?
console.log(citySelector.select()); // 闅忔満杩斿洖鍩庡競鍚?

馃挕 澶嶆潅搴﹀垎鏋愶細

• 棰勫鐞嗘椂闂达細O(n)
• 姣忔鏌ヨ鏃堕棿锛歄(log n)
• 绌洪棿澶嶆潅搴︼細O(n)

涓夈€佹墿灞曢鐩細BST涓煡鎵炬渶鎺ヨ繎鐩爣鐨勫€?/h2>

3.1 闂鎻忚堪

缁欏畾涓€妫典簩鍙夋悳绱㈡爲鍜屼竴涓洰鏍囧€硷紝鎵惧埌鏍戜腑涓庣洰鏍囧€兼渶鎺ヨ繎鐨勮妭鐐瑰€笺€?/p>

3.2 鍒╃敤BST鐗规€х殑瑙ｆ硶

interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}

function findClosestValue(root: TreeNode | null, target: number): number {
    let closest = root?.val ?? 0;
    let minDiff = Math.abs(closest - target);
    
    let current = root;
    
    while (current !== null) {
        const currentDiff = Math.abs(current.val - target);
        
        // 鏇存柊鏈€鎺ヨ繎鍊?
        if (currentDiff < minDiff) {
            minDiff = currentDiff;
            closest = current.val;
        }
        
        // 瀹屽叏鍖归厤锛岀洿鎺ヨ繑鍥?
        if (currentDiff === 0) {
            return closest;
        }
        
        // 鍒╃敤BST鎬ц川閫夋嫨鎼滅储鏂瑰悜
        if (target < current.val) {
            current = current.left;   // 鐩爣鏇村皬锛屽線宸﹀瓙鏍戞壘
        } else {
            current = current.right;  // 鐩爣鏇村ぇ锛屽線鍙冲瓙鏍戞壘
        }
    }
    
    return closest;
}

3.3 绠楁硶鍘熺悊

BST鐨勭壒鎬у喅瀹氫簡锛?/p>

• 宸﹀瓙鏍戞墍鏈夎妭鐐?< 褰撳墠鑺傜偣
• 鍙冲瓙鏍戞墍鏈夎妭鐐?> 褰撳墠鑺傜偣

鍥犳锛屼粠鏍硅妭鐐瑰嚭鍙戯紝姣忔鏍规嵁鐩爣鍊间笌褰撳墠鑺傜偣鐨勫ぇ灏忓叧绯伙紝閫夋嫨寰€宸︽垨寰€鍙宠蛋锛?strong>璺緞涓婁竴瀹氫細缁忚繃娼滃湪鐨勬渶浼樿В銆?/p>

鍥涖€佺畻娉曞姣旀€荤粨

绠楁硶	搴旂敤鍦烘櫙	鏃堕棿澶嶆潅搴?/th>
鍔犳潈闅忔満閲囨牱	鎸夋鐜囬殢鏈洪€夋嫨	O(log n)
BST鏈€杩戝€兼煡鎵?/td>	鏌ユ壘鏈€鐩镐技鍏冪礌	O(h)

鍏朵腑 h 涓烘爲鐨勯珮搴︼紝骞宠　BST鏃?h = O(log n)

浜斻€侀潰璇曟妧宸?/h2>

1. 鏄庣‘姒傜巼瑕佹眰锛氱‘璁ゆ槸绮剧‘姒傜巼杩樻槸杩戜技姒傜巼
2. 璁ㄨ杈圭晫鎯呭喌锛氭潈閲嶄负0銆佽礋鏉冮噸銆佺┖杈撳叆绛?/li>
3. 鑰冭檻娴偣绮惧害锛氬繀瑕佹椂浣跨敤鏁存暟杩愮畻閬垮厤绮惧害闂
4. 鍔ㄦ€佹洿鏂板満鏅?/strong>锛氬闇€棰戠箒淇敼鏉冮噸锛岃€冭檻绾挎鏍戠瓑楂樼骇缁撴瀯

姒傜巼绠楁硶 鍓嶇紑鍜?/span> 浜屽垎鏌ユ壘 BST 鍔犳潈閲囨牱