有一批订单记录,数据有订单号,入店时间,离店时间;
输入一个时间值A,需要在这批记录中找到符合入离店时间范围(A大于等于入店时间,并且A小于等于离店时间)内的所有记录。 单次查询时间复杂度控制在O(logN)
※注意:订单号升序输出
记录数:10
时间值A:20180602
订单号 入店时间 离店时间
1001 20180103 20180105
1002 20180202 20180203
1003 20180304 20180306
1004 20180401 20180408
1005 20180501 20180504
1006 20180601 20180604
1007 20180705 20180706
1008 20180801 20180804
1009 20180903 20180903
1010 20181003 20181003
以上输入都为整型
1006
10 20180602 1001 20180103 20180105 1002 20180202 20180203 1003 20180304 20180306 1004 20180401 20180408 1005 20180501 20180504 1006 20180601 20180604 1007 20180705 20180706 1008 20180801 20180804 1009 20180903 20180903 1010 20181003 20181003
1006
5 20170103 1013 20180103 20180105 1022 20180102 20180103 1103 20180104 20180106 1034 20180101 20180102 1105 20180201 20180204
null
查不到时输出null字符串(小写)
4 20180103 1013 20180103 20180105 1022 20180102 20180103 1026 20180103 20180103 1007 20180101 20180109
1007 1013 1022 1026
没有什么特别好的办法啊,只能对入住时间排序,然后采用二分查找,再验证离开时间是否满足要求,如果有更好的解法,麻烦@我一下,谢谢。
#include <bits/stdc++.h> using namespace std; struct Dindan { long num, in, out; }; bool cmp(Dindan a, Dindan b) { return a.in < b.in; } int BinarySearch(vector<Dindan> v, int data) { int left = 0, right = v.size(); while (left < right) { int mid = (left + right) / 2; if (v[mid].in <= data) left = mid + 1; else right = mid; } return left; } int main() { int n, data; cin >> n >> data; vector<Dindan> v(n); for (int i = 0; i < n; i++) cin >> v[i].num >> v[i].in >> v[i].out; sort(v.begin(), v.end(), cmp); vector<int> res; int end = BinarySearch(v, data); for (int i = 0; i < end; i++) if (v[i].out >= data) res.push_back(v[i].num); if (res.empty()) { cout << "null" << endl; } else { sort(re***egin(), res.end()); for (int i : res) cout << i << endl; } system("pause"); return 0; }
#include <stdio.h> #include <stdlib.h> typedef struct { int id; /** 订单ID */ int in_time; /** 到店时间 */ int out_time; /** 离店时间 */ } Order; // =============== function prorotype =============== // 按订单的到店时间升序排序(由小至大) int compare_1(const void* a, const void* b); // 按订单的离店时间升序排序(由小至大) int compare_2(const void* a, const void* b); int compare_3(const void* a, const void* b); // 打印所有的订单信息 void printOrders(Order orders[], const int size); // =============== function prorotype =============== // global variable int (*cmp)(const void*, const void*) = compare_1; int main(void) { int i, n, a, sz; scanf("%d %d", &n, &a); Order orders[n]; for (i = 0; i < n; ++i) { scanf("%d %d %d", &orders[i].id, &orders[i].in_time, &orders[i].out_time); // printf("%d %d %d\n", orders[i].id, orders[i].in_time, orders[i].out_time); } qsort(orders, n, sizeof(Order), cmp); // 二分查找法: // Template: [low, high) int low = 0, high = n, middle; while (low < high) { middle = low + ((high - low) >> 1); if (orders[middle].in_time > a) // 寻找最左边 > a ,变相就是寻找最右边 <= a high = middle; // 收缩右边界 else low = middle + 1; // 收缩左边界 } sz = low; Order tmp[sz]; // 保存了到店时间早于或等于A的所有订单 memcpy(tmp, orders, sz * sizeof(Order)); cmp = compare_2; qsort(tmp, sz, sizeof(Order), cmp); low = 0, high = sz; while (low < high) { middle = low + ((high - low) >> 1); if (tmp[middle].out_time >= a) // be careful!! high = middle; // 收缩右边界 else low = middle + 1; // 收缩左边界 } sz -= low; if (!sz) return puts("null"), 0; int ret[sz]; for (i = 0; i < sz; ++i) ret[i] = tmp[low + i].id; cmp = compare_3; qsort(ret, sz, sizeof(int), cmp); for (i = 0; i < sz; ++i) printf("%d\n", *(ret + i)); return 0; } int compare_1(const void* a, const void* b) { return ((Order*) a)->in_time - ((Order*) b)->in_time; } int compare_2(const void* a, const void* b) { return ((Order*) a)->out_time - ((Order*) b)->out_time; } int compare_3(const void* a, const void* b) { return *((int*) a) - *((int*) b); } void printOrders(Order orders[], const int size) { int i; printf("%-15s%-15s%-15s\n", "订单号", "到店时间", "离店时间"); for (i = 0; i < size; ++i) printf("%-15d%-15d%-15d\n", orders[i].id, orders[i].in_time, orders[i].out_time); putchar('\n'); }
#include <bits/stdc++.h> using namespace std; struct P{ int id, s, e; }; int main(){ int n, t, cnt=0; cin>>n>>t; P p[n]; set<int> v; for(int i=0;i<n;i++){ cin>>p[i].id>>p[i].s>>p[i].e; if(p[i].s<=t && p[i].e>=t) v.insert(p[i].id); } if(v.size()==0) cout<<"null"<<endl; else{ for(auto s: v) cout<<s<<endl; } return 0; }
importjava.util.*;public clas***ain{public static void main(String[] args) {Scanner in = new Scanner(System.in);intx = in.nextInt();//记录数;intA = in.nextInt();//时间值;int[][] a = newint[x][3];//记录信息;for(inti = 0; i <x ; i++) {for(intj = 0; j <3; j++) {a[i][j] = in.nextInt();}}TreeSet<Integer> set = new TreeSet<Integer>();for(inti = 0; i < x ; i++) {for(intj = 0; j < 3; j++) {if(a[i][1] <= A && A <= a[i][2]){set.add(a[i][0]);}}}if(set.size()==0)System.out.println("null");Iterator it = set.iterator();intk = 0;while(it.hasNext())//判断是否有下一个{k = (int) it.next();System.out.println(k);}}}
#include "bits/stdc++.h"using namespace std;typedef struct Dingdan{string id;string startDate;string endDate;} DD;int main(){int n;string date;while(cin>>n>>date){cin.ignore();vector<DD> vec(n);string str;vector<string> ans;for(int i=0;i<n;i++){getline(cin,str);stringstream ss(str);ss>>vec[i].id>>vec[i].startDate>>vec[i].endDate;}for(int i=0;i<n;i++){if(vec[i].startDate<=date&&vec[i].endDate>=date)ans.push_back(vec[i].id);}sort(ans.begin(),ans.end());if(ans.empty())cout<<"null"<<endl;elsefor(auto i:ans)cout<<i<<endl;}}
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int a; cin>>a; vector<int>num(n),r(n),c(n),res; for(int i=0;i<n;i++) { cin>>num[i]>>r[i]>>c[i]; if(a>=r[i]&&a<=c[i]) res.push_back(num[i]); } if(res.size()==0) cout<<"null"<<endl; else { sort(res.begin(),res.end()); for(int i=0;i<res.size();i++) cout<<res[i]<<endl; } return 0; }
import java.util.*; public clas***ain { static clas***ill{ int id; int inTime; int outTime; public bill(int id, int inTime, int outTime) { this.id = id; this.inTime = inTime; this.outTime = outTime; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int A = in.nextInt(); int[] ids = new int[n]; int[] inTimes = new int[n]; int[] outTimes = new int[n]; bill[] bills = new bill[n]; for (int i = 0; i < n; i++) { bills[i] = new bill(0,0,0); bills[i].id = in.nextInt(); bills[i].inTime = in.nextInt(); bills[i].outTime = in.nextInt(); } Arrays.sort(bills, (o1, o2) -> o1.inTime - o2.inTime); for (int i = 0; i < n; i++) { ids[i] = bills[i].id; inTimes[i] = bills[i].inTime; outTimes[i] = bills[i].outTime; } int re***S(A, inTimes); boolean isNull = true; List<Integer> out = new ArrayList<>(); for (int i = 0; i <= res; i++) { if (inTimes[res] <= A && outTimes[i] >= A) { //System.out.println(ids[i]); out.add(ids[i]); isNull = false; } } out.sort(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o1 - o2; } }); if (isNull) { System.out.println("null"); } else { for (int i = 0; i < out.size(); i++) { System.out.println(out.get(i)); } } } static int BS(int target, int[] nums) { int l = 0; int r = nums.length - 1; while (l + 1 < r) { int mid = l + ((r - l) >> 1); if (num***id] > target) { r = mid; } else if (num***id] <= target) { l = mid; } } if (nums[r] == target) return r; return l; } }
package mainimport ("fmt""sort")func main(){var n, time intfmt.Scanln(&n)fmt.Scanln(&time)var ans []intfor i := 0; i < n; i++ {var seq, startTime, endTime intfmt.Scanln(&seq, &startTime, &endTime)if endTime - startTime >= endTime - time&& (endTime - time) >= 0 {ans = append(ans, seq)}}if len(ans) == 0 {fmt.Println("null")} else {sort.Ints(ans)for _, v := range ans {fmt.Println(v)}}}
/* 思路:把入店和离店时间转成int,然后与给定的时间进行比较,符合条件的存入集合 ※注意:订单号升序输出,sort方法 */ import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.ArrayList; import java.util.Collections; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int timeA = Integer.parseInt(br.readLine()); //int count = 0; ArrayList<Integer> list = new ArrayList<>(); for(int i = 0;i < n;i++){ String[] str = br.readLine().split(" "); int orderid = Integer.parseInt(str[0]); int intime = Integer.parseInt(str[1]); int outtime = Integer.parseInt(str[2]); if(timeA >= intime && timeA <= outtime){ list.add(orderid); } } if(list.isEmpty()) System.out.println("null"); else{ Collections.sort(list); for(Object obj:list) System.out.println(obj); } } }
#include <bits/stdc++.h> using namespace std; int main(){ int n; int time; cin>>n>>time; vector<int> ans; for(int i=0;i<n;i++){ int id,t1,t2; cin>>id>>t1>>t2; if(t1<=time&&t2>=time) ans.push_back(id); } if(ans.empty()){ cout<<"null"; return 0; } sort(ans.begin(),ans.end()); for(int i:ans) cout<<i<<endl; return 0; }
我的方法比较死板,但还好有效的,直接在输入的时候进行插入排序(根据ID),最后遍历输出。 package cn.bubbletg.test; import java.util.Scanner; public class test { public static void main(String args[]) { Scanner in = new Scanner(System.in); //输入 int N = in.nextInt(); int date = in.nextInt(); dingdan[] dd = new dingdan[N]; for (int i = 0; i < N; i++) { dd[i] = new dingdan(); } dd[0].id = in.nextInt(); dd[0].date_q = in.nextInt(); dd[0].date_h = in.nextInt(); //直接使用插入排序 for (int i = 1; i < N; i++) { dd[i].id = in.nextInt(); dd[i].date_q = in.nextInt(); dd[i].date_h = in.nextInt(); //无序部分第一个值,即待插入值 int value = dd[i].id; int valueq = dd[i].date_q; int valueh = dd[i].date_h; //有序部分最后一个值 int yw = i - 1; //插入位置结束条件 while (yw >= 0 && dd[yw].id > value) { //待插入值先前移动,有序部分向后移动 dd[yw + 1].id = dd[yw].id; dd[yw + 1].date_q = dd[yw].date_q; dd[yw + 1].date_h = dd[yw].date_h; //让待插入值与有序部分倒数第(yw+) 比较 yw--; } //待插入值插入,因为退出循环,说明位置找到(yw+1) dd[yw + 1].id = value; dd[yw + 1].date_q = valueq; dd[yw + 1].date_h = valueh; } boolean t = false; //按条件输出 for (int i = 0; i < N; i++) { if (dd[i].date_q <= date && dd[i].date_h >= date) { System.out.println(dd[i].id); t = true; } } if (!t) { System.out.println("null"); } } } class dingdan { //订单号 public Integer id; public Integer date_q; public Integer date_h; }
import java.lang.reflect.Array; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int target = sc.nextInt(); int[][] nums = new int[n][3]; for(int i = 0; i < n; i++){ for(int j = 0; j < 3; j++){ nums[i][j] = sc.nextInt(); } } Arrays.sort(nums, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[1] - o2[1]; } }); List<Integer> res = new ArrayList<>(); getRes(res, nums, target, 0, nums.length - 1); if(res.isEmpty()){ System.out.println("null"); return ; } Collections.sort(res); for(int temp : res){ System.out.println(temp); } } private static void getRes(List<Integer> res, int[][] nums, int target, int l, int h) { if(l > h) return ; int mid = l + (h - l) / 2; if(nums[mid][1] <= target && nums[mid][2] >= target){ res.add(nums[mid][0]); } getRes(res, nums, target, l, mid - 1); getRes(res, nums, target , mid + 1, h); } }
直接对输入判断,将合适的id放进一个数组里排序后把0过滤掉再输出
import java.util.Arrays; import java.util.Scanner; public class Test { public static void main(String args[]) { Scanner scan = new Scanner(System.in); int N = scan.nextInt(); int A = scan.nextInt(); dingdan[] dd = new dingdan[N]; for(int i = 0; i < N; i++) { dd[i] = new dingdan(); } for(int i = 0; i < N ; i++) { dd[i].id = scan.nextInt(); dd[i].inTime = scan.nextInt(); dd[i].outTime = scan.nextInt(); } boolean ans = false; int []arr = new int[N]; for(int i = 0; i < N ; i++) { if(A = dd[i].inTime) { arr[i] = dd[i].id; ans = true; } } Arrays.sort(arr); if(ans==false) { System.out.println("null"); }else { for(int i = 0; i < N ; i++) { if(arr[i]==0) { System.out.print(""); }else { System.out.println(arr[i]); } } } } } class dingdan { int id; int inTime; int outTime; }
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; int main() { int number; int time; int res[101]; int j = 0; int temp = 1; int flag = 0; scanf("%d", &number); scanf("%d", &time); int a[1024][3]; int t[3]; for(int i = 0; i < number; i++){ scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]); } for(int i = 0; i < number; i++){ for(int k = i + 1; k < number; k++){ if(a[i][1] > a[k][1]){ t[0] = a[i][0]; t[1] = a[i][1]; t[2] = a[i][2]; a[i][0] = a[k][0]; a[i][1] = a[k][1]; a[i][2] = a[k][2]; a[k][0] = t[0]; a[k][1] = t[1]; a[k][2] = t[2]; } } } int left = 0; int right = number - 1; int middle = 0; res[j] = -1; int n = number; while(n--){ middle = (left + right) / 2; if(time >= a[middle][1] && time <= a[middle][2]){ res[j] = a[middle][0]; j++; while(1){ flag = 0; if(middle - temp >= 0 && time >= a[middle - temp][1] && time <= a[middle - temp][2]){ res[j++] = a[middle - temp][0]; flag = 1; } res[j] = a[middle - temp][0]; if(middle + temp <= number -1 && time >= a[middle + temp][1] && time <= a[middle + temp][2]){ res[j++] = a[middle + temp][0]; flag = 1; } temp++; if(!flag){ break; } } break; } if(time > a[middle][2]){ left = middle; } if(time < a[middle][1]){ right = middle; } } sort(res, res + j); if(res[j] != -1){ for(int i = 0; i < j; i++){ printf("%d\n", res[i]); } }else { printf("null"); } return 0; }用例全过,但是不清楚是方法正确还是偶然过了所有用例。
#!/bin/bash read num read target sig=0 A=() while [ $num -gt 0 ] do read index minimum miximum if [ "$target" -ge "$minimum" ] && [ "$target" -le "$miximum" ] then sig=1 A[${#A[@]}]=$index fi num=$(($num-1)) done if [ $sig -eq 0 ] then echo "null" else echo ${A[@]} | tr " " "\n" | sort -n fi
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int A = sc.nextInt(); Set<Integer> result = new TreeSet<>(); Map<Integer, Set<Integer>> map = new HashMap<>(); for(int i=0;i<n;i++){ int key = sc.nextInt(); int startTime = sc.nextInt(); int endTime = sc.nextInt(); Set<Integer> set = new TreeSet<>(); for(int j=startTime;j<=endTime;j++){ set.add(j); } if(set.contains(A)){ result.add(key); } } if(!result.isEmpty()){ for(Integer number:result){ System.out.println(number); } }else{ System.out.println("null"); } } }充分利用Java集合,做完才发现和大家思路都不一样,感觉好像钻了空子