ruby daily practice 1

原创文章,转载请注明来源并保留原文链接

题目:在排序数组中,找出给定数字的出现次数,比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。

最简单的方法

# 给定数组
arr = [224698362469]

# 使用count函数
arr.count(2)  #=> 3

arr.count(1)  #=> 0

So Easy

不过题目不会考你api方法的,考的应该是算法
二分搜索查找,时间复杂度O(log n)。

# 给Array添加新的instance_method
class Array
 def new_count(num, need_sort = true )
 # 初始为0
 count = 0
 return count if empty?
 # 排序  只有第一次需要
 sort_arr = need_sort ? self.sort : self   
 index = sort_arr.length/2
 last_index = sort_arr.length - 1
 # 取得中间的数    
 middle = sort_arr.at(index)
 if middle == num
   # 因为匹配成功才扫描,所以肯定有一个存在
   count = 1     
   # 向前扫描    
   (index -1).downto(0) do |idx|
     if sort_arr.at(idx) == num
  count += 1
     else
        break
     end
   end
   # 向后扫描
   (index + 1).upto(last_index) do |idx|
  if sort_arr.at(idx) == num
      count += 1
  else
     break
   end
    end
  elsif middle > num
  sort_arr[0..(index -1)].new_count(num,false)
  elsif middle < num
  sort_arr[(index + 1)..(last_index - 1)].new_count(num,false)     
  end
  return count
  end
end

# 测试
[1,4,4,3,4,4,4].new_count(3) # => 1
[1,4,4,3,4,2,4].new_count(4) # => 4

Leave a Reply

Your email address will not be published. Required fields are marked *