Binary Search

今日練習的題目是 300. Longest Increasing Subsequence 主要是需要使用到 Binary Search

首先是 C++ 的 lower_bound

class Solution {
public:
    int lengthOfLIS(vector< int>& nums) {
        vector< int> arr;
        arr.reserve(nums.size());
        for (auto& num : nums) {
            auto ptr = ranges::lower_bound(arr.begin(), arr.end(), num);
            if (ptr == arr.end()) {
                arr.push_back(num);
            } else {
                *ptr = num;
            }
        }
        return arr.size();
    }
};

然後是 Python 的 bisect.bisect_left()

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        arr = []
        for num in nums:
            i = bisect.bisect_left(arr, num)
            if i == len(arr):
                arr.append(num)
            else:
                arr[i] = num
        return len(arr)

然後是 Go 的 sort.Search()

func lengthOfLIS(nums []int) int {
	arr := make([]int, 0, len(nums))
	for _, num := range nums {
		idx := sort.Search(len(arr), func(i int) bool {
			return arr[i] >= num
		})
		if idx == len(arr) {
			arr = append(arr, num)
		} else {
			arr[idx] = num
		}
	}
	return len(arr)
}

最後是 Rust 的 binary_search

impl Solution {
    pub fn length_of_lis(nums: Vec< i32>) -> i32 {
        let mut arr = Vec::with_capacity(nums.len());
        for num in nums {
            let i = match arr.binary_search(&num) {
                Ok(index) => index,
                Err(index) => index,
            };
            if i == arr.len() {
                arr.push(num);
            } else {
                arr[i] = num;
            }
        }
        arr.len() as i32
    }
}

每種程式語言使用方式都有所不同。