首页 > 代码库 > 九度 1349 数字在排序数组中出现的次数
九度 1349 数字在排序数组中出现的次数
package com.wangzhu.njupt;import java.io.BufferedInputStream;import java.io.FileInputStream;import java.io.IOException;import java.io.StreamTokenizer;/** * 在已排序的数组中查找数出现的次数 * * @ClassName: Main1349 * @Description: TODO * @author 王竹 * @date 2014-10-5 下午5:02:27 * */public class Main1349 { private static final int LEN = 1000001; private static int[] arr = new int[LEN]; /** * @param args * @throws IOException */ public static void main(String[] args) throws IOException { //System.setIn(new FileInputStream("data.in")); StreamTokenizer in = new StreamTokenizer(new BufferedInputStream( System.in)); while (in.nextToken() != StreamTokenizer.TT_EOF) { int n = (int) in.nval; for (int i = 0; i < n; i++) { in.nextToken(); arr[i] = (int) in.nval; } in.nextToken(); int t = (int) in.nval; for (int i = 0; i < t; i++) { in.nextToken(); int m = (int) in.nval; int index = binarySearch(n, m); int count = 0; if (index != -1) { count++; int j = index - 1; while (j >= 0 && arr[j--] == m) { count++; } j = index + 1; while (j < n && arr[j++] == m) { count++; } } System.out.println(count); } } } /** * 二分查找 * * @param len * @param key * @return */ private static int binarySearch(int len, int key) { int left = 0, right = len - 1; while (left <= right) { int mid = (left + right) >> 1; if (arr[mid] > key) { right = mid - 1; } else if (arr[mid] < key) { left = mid + 1; } else { return mid; } } return -1; }}
九度 1349 数字在排序数组中出现的次数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。