Cannot use the `?` operator in a function that returns `std::vec::Vec<i32>`

1

I was wirting a leetcode problem.and encoutered this error:

pub fn next_greater_element(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
    let mut ret = Vec::new();
    let mut next_g = -1;
    for i in nums1 {
        let mut tmp = nums2.binary_search(&i)?;
        for j in (tmp+1)..nums2.len() {
            if nums2[j] > i {
                next_g = nums2[j];
                break;
            }
        }
        ret.push(next_g);
        next_g = -1;
    }
    ret
}

error[E0277]: the `?` operator can only be used in a function that returns `Result` or `Option` (or another type that implements `std::ops::Try`)
   --> src\main.rs:590:23
    |
590 |         let mut tmp = (nums2.binary_search(&i))?;
    |                       ^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot use the `?` operator in a function that returns `std::vec::Vec<i32>`
    |
    = help: the trait `std::ops::Try` is not implemented for `std::vec::Vec<i32>`
    = note: required by `std::ops::Try::from_error`

But the return type of the function binary_search is a Result.
The Clion IDE also indicates this.

image
image750×367 8.02 KB

2

If you are sure that everything in nums1 is contained in nums2, you can replace the line by:

let mut tmp = match nums2.binary_search(&i) {
    Ok(val) => val,
    _ => unreachable!()
};

Otherwise replace the return type by Result<Vec<i32>,usize>.

3

image
image1213×836 32.2 KB

It didn't work
.
i = 4, then search 4 in nums2, but it goes to unreachable.what's wrong with my code?

4

From the doc on binary_search:

If the value is found then Result::Ok is returned, containing the index of the matching element. If there are multiple matches, then any one of the matches could be returned. If the value is not found then Result::Err is returned, containing the index where a matching element could be inserted while maintaining sorted order.

So if you want the index of the smallest element larger than the argument to binary_search, you should take the next if found, but if not found, just get the index:

let next_g_index = match nums2.binary_search(&i) {
    Ok(i) => i + 1,
    Err(i) => i,
};
if next_g_index < nums2.len() {
    ret.push(nums2[next_g_index]);
} else {
    // ...?
}

What do you want to do if &i is larger than anything in nums2?

5

Note that there is also a linear time solution that iterates over both arrays in lockstep.

6

Note that binary_search expects the slice to be sorted. You can define

fn is_sorted<T>(a: &[T]) -> bool where T: Ord {
    a.windows(2).all(|t| t[0] <= t[1])
}

and add a precondition

pub fn next_greater_element(nums1: &[i32], nums2: &[i32]) -> Vec<i32> {
    assert!(is_sorted(&nums2));
    // ...
}
7

Uhh, well I suppose that if nums2 has many equal elements, you need to handle that.

let next_g_index = match nums2.binary_search(&i) {
    Ok(i) => {
         let mut i = i + 1;
         while i < nums2.len() && nums2[i] == i { i += 1; }
         i
    },
    Err(i) => i,
};

Unfortunately this makes your algorithm O(n^2) in the worst case.

8

Though if you binary search for i + 1 instead, it should work without the expensive inner loop.

let next_g_index = match nums2.binary_search(&(i + 1)) {
    Ok(i) => i, // this might not be the first such index, but it's ok because we only care about the value at the index
    Err(i) => i,
};
9

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.