javascript 解法, 执行用时: 0 ms, 内存消耗: 49.9 MB, 提交时间: 2025-02-17 09:28:37

/**
 * @param {number[]} arr
 * @return {number}
 */
var findSpecialInteger = function(arr) {
    const m = Math.floor(arr.length / 4);
    for (const i of [m, m * 2 + 1]) {
        const x = arr[i];
        const j = _.sortedIndex(arr, x);
        if (arr[j + m] == x) {
            return x;
        }
    }
    return arr[m * 3 + 2];
};

cpp 解法, 执行用时: 0 ms, 内存消耗: 15.8 MB, 提交时间: 2025-02-17 09:28:24

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int m = arr.size() / 4;
        for (int i : {m, m * 2 + 1}) {
            int x = arr[i];
            int j = ranges::lower_bound(arr, x) - arr.begin();
            if (arr[j + m] == x) {
                return x;
            }
        }
        return arr[m * 3 + 2];
    }
};

java 解法, 执行用时: 0 ms, 内存消耗: 43.9 MB, 提交时间: 2025-02-17 09:28:11

class Solution {
    public int findSpecialInteger(int[] arr) {
        int m = arr.length / 4;
        for (int i : new int[]{m, m * 2 + 1}) {
            int x = arr[i];
            int j = lowerBound(arr, x);
            if (arr[j + m] == x) {
                return x;
            }
        }
        return arr[m * 3 + 2];
    }

    // lowerBound 返回最小的满足 nums[i] >= target 的下标 i
    // 如果数组为空，或者所有数都 < target，则返回 nums.length
    // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
    // 原理见 https://www.bilibili.com/video/BV1AP41137w7/
    private int lowerBound(int[] nums, int target) {
        int left = -1;
        int right = nums.length; // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid; // 范围缩小到 (left, mid)
            } else {
                left = mid; // 范围缩小到 (mid, right)
            }
        }
        // 循环结束后 left+1 = right
        // 此时 nums[left] < target 而 nums[right] >= target
        // 所以 right 就是第一个 >= target 的元素下标
        return right;
    }
}

rust 解法, 执行用时: 0 ms, 内存消耗: 2.5 MB, 提交时间: 2025-02-17 09:27:57

impl Solution {
    pub fn find_special_integer(arr: Vec<i32>) -> i32 {
        let m = arr.len() / 4;
        for i in [m, m * 2 + 1] {
            let x = arr[i];
            let j = arr.partition_point(|&y| y < x);
            if arr[j + m] == x {
                return x;
            }
        }
        arr[m * 3 + 2]
    }
}

golang 解法, 执行用时: 0 ms, 内存消耗: 6.6 MB, 提交时间: 2025-02-17 09:26:43

func findSpecialInteger(arr []int) int {
    m := len(arr) / 4
    for _, i := range []int{m, m*2 + 1} {
        x := arr[i]
        j := sort.SearchInts(arr, x)
        if arr[j+m] == x {
            return x
        }
    }
    return arr[m*3+2]
}

python3 解法, 执行用时: 0 ms, 内存消耗: 18.5 MB, 提交时间: 2025-02-17 09:26:29

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        m = len(arr) >> 2
        for i in (m, m * 2 + 1):
            x = arr[i]
            j = bisect_left(arr, x)
            if arr[j + m] == x:
                return x
        return arr[m * 3 + 2]

python3 解法, 执行用时: 0 ms, 内存消耗: 18.3 MB, 提交时间: 2025-02-17 09:24:58

class Solution:
    # 使用集合函数
    def findSpecialInteger1(self, arr: List[int]) -> int:
        c = Counter(arr)
        return c.most_common()[0][0]
        
    # 基于递增特性
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        step = n >> 2
        for i in range(0, n-step):
            if arr[i] == arr[i+step]: return arr[i]
        return -1

golang 解法, 执行用时: 12 ms, 内存消耗: 4.9 MB, 提交时间: 2021-06-10 23:30:04

func findSpecialInteger(arr []int) int {
    n := len(arr)
    step := n >> 2
    for i := 0; i < n - step; i++ {
        if arr[i] == arr[i+step] {
            return arr[i]
        }
    }
    return -1
}