做网站的那家公司好,建立网站一般包括什么等方式,淘宝上网站建设续费,亚马逊品牌注册网站建设Problem: 蓝桥杯 递增三元组 文章目录 思路解题方法复杂度前缀和Code二分Code双指针Code 思路 这是一个关于数组的问题#xff0c;我们需要找到一个递增的三元组。这个三元组由三个数组中的元素组成#xff0c;每个数组提供一个元素#xff0c;并且这三个元素满足递增的关系… Problem: 蓝桥杯 递增三元组 文章目录 思路解题方法复杂度前缀和Code二分Code双指针Code 思路 这是一个关于数组的问题我们需要找到一个递增的三元组。这个三元组由三个数组中的元素组成每个数组提供一个元素并且这三个元素满足递增的关系。 解题方法 我们可以使用三种方法来解决这个问题前缀和二分查找和双指针。 1、前缀和我们首先对数组a和c进行计数然后计算出前缀和。然后我们遍历数组b对于每一个元素bi我们找到数组a中小于bi的元素数量和数组c中大于bi的元素数量然后将这两个数量相乘累加到结果中。 2、二分查找我们首先对数组a和c进行排序。然后我们遍历数组b对于每一个元素bi我们使用二分查找在数组a中找到小于bi的最大元素的位置和在数组c中找到大于bi的最小元素的位置然后将这两个位置相乘累加到结果中。 3、双指针我们首先对数组ab和c进行排序。然后我们使用两个指针一个指向数组a的开始一个指向数组c的开始。我们遍历数组b对于每一个元素bi我们移动数组a的指针直到找到一个大于或等于bi的元素然后移动数组c的指针直到找到一个大于bi的元素然后将这两个位置相乘累加到结果中。 复杂度
时间复杂度: 对于前缀和和双指针方法时间复杂度为 O ( n ) O(n) O(n)。对于二分查找方法时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。 空间复杂度: 对于所有的方法空间复杂度都为 O ( n ) O(n) O(n)。 前缀和Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Main {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr new StreamTokenizer(in);static int MAXN (int) (1e5 10);static int[] a new int[MAXN];static int[] b new int[MAXN];static int[] c new int[MAXN];static int[] as new int[MAXN];static int[] cs new int[MAXN];static int n;public static void main(String[] args) throws IOException {n nextInt();for (int i 0; i n; i) {a[i] nextInt();}for (int i 0; i n; i) {b[i] nextInt();}for (int i 0; i n; i) {c[i] nextInt();}for (int i 0; i n; i) {as[a[i]];cs[c[i]];}// 计算出前缀和for (int i 1; i MAXN; i) {as[i] as[i - 1];cs[i] cs[i - 1];}long res 0;// 枚举枚举每一个bifor (int i 0; i n; i) {if (b[i] 0) {continue;}res (long) as[b[i] - 1] * (long) (cs[MAXN - 1] - cs[b[i]]);}out.println(res);out.flush();}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}
二分Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Main {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr new StreamTokenizer(in);static int MAXN (int) (1e5 10);static int[] a new int[MAXN];static int[] b new int[MAXN];static int[] c new int[MAXN];static int n;public static void main(String[] args) throws IOException {n nextInt();for (int i 0; i n; i) {a[i] nextInt();}for (int i 0; i n; i) {b[i] nextInt();}for (int i 0; i n; i) {c[i] nextInt();}Arrays.sort(a, 0, n);Arrays.sort(c, 0, n);// 二分查找 小于bi最右边的数字 目的尽可能多// 大于bi最左边的数字 目的是让数字尽可能多long res 0;for (int i 0; i n; i) {int left getA(0, n - 1, b[i]);int right getB(0, n - 1, b[i]);res (long) (left 1) * (n - right);}out.println(res);out.flush();}private static int getA(int l, int r, int x) {// TODO Auto-generated method stubwhile (l r) {int mid (l r 1) / 2;if (a[mid] x) {l mid;} else {r mid - 1;}}return a[l] x ? l : -1;}private static int getB(int l, int r, int x) {// TODO Auto-generated method stubwhile (l r) {int mid (l r) / 2;if (c[mid] x) {r mid;} else {l mid 1;}}return c[r] x ? r : n;}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}
双指针Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Main {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr new StreamTokenizer(in);static int MAXN (int) (1e5 10);static int[] a new int[MAXN];static int[] b new int[MAXN];static int[] c new int[MAXN];static int n;public static void main(String[] args) throws IOException {n nextInt();for (int i 0; i n; i) {a[i] nextInt();}for (int i 0; i n; i) {b[i] nextInt();}for (int i 0; i n; i) {c[i] nextInt();}Arrays.sort(a, 0, n);Arrays.sort(b, 0, n);Arrays.sort(c, 0, n);// 使用双指针算法long res 0;for (int i 0, ai 0, ci 0; i n; i) {while (ai n a[ai] b[i]) {ai;}while (ci n c[ci] b[i]) {ci;}res (long) ai * (n - ci);}out.println(res);out.flush();}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}
