问题描述:

Need help with this homework problem. How do I write a function, nearest_larger(arr, i) which takes an array and an index. The function should return another index. The conditions are below. Thanks.

This should satisfy:

(a) `arr[i] < arr[j]`, AND

(b) there is no `j2` closer to `i` than `j` where `arr[i] < arr[j]`.

In case of ties (see example beow), choose the earliest (left-most) of the two indices. If no number in arr is largr than arr[i], return nil.

example:

nearest_larger([2,3,4,8], 2).should == 3

end

My code is:

def nearest_larger(arr, idx)

greater_nums = []

arr.each {|element| greater_nums << element if element>idx}

sorted_greater_nums= greater_nums.sort

nearest_larger = sorted_greater_nums[0]

arr.index(nearest_larger)

end

THANKS a lot guys. See post below for solution

网友答案:

I see at least two mistakes here.

First, your code seems to assume the array is sorted. (Otherwise why would taking the least of greater_nums give you the closest index?) But from your requirements (choose the left-most index in case of a tie), that is clearly not guaranteed.

More importantly, in your each loop you're comparing element to idx (the index passed in) rather than arr[idx].

I think what you really want to do is something like this:

def nearest_larger(arr, idx)
  value = arr[idx]

  # Ensure idx is actually valid.
  return nil if idx < 0 || idx >= arr.length

  left, right = [idx - 1, idx + 1]
  while (left >= 0 || right < arr.length)
    # Always check left first, per the requirement.
    return left if left >= 0 && arr[left] > value
    return right if right < arr.length && arr[right] > value

    # Incrementally move farther and farther left/right from the specified index
    # looking for a larger value.
    left, right = [left - 1, right + 1]
  end

  # This will return nil if no values were larger than arr[idx].
end
相关阅读:
Top