Java

顺序统计的问题是： 给定一组元素，找到其中第k大（小）的元素 仅从功能实现上考虑，完全可以先对数组排序，然后直接取nums[k-1]作为结果输出。但这个方法是需要先对数组排序的，所以效率为$\Theta(nlogn)$，我们的目标是找到一种$\Theta(n)$的方法 基于随机数的分治法 为了尽量压缩时间，可以考虑能不能在排序进行时就顺便找到所需元素，为此，可以使用快速排序算法中的分治思想 在快速排序算法中，每选定一个基准数pivot，就需要将所有小于pivot的元素移动至其左侧、所有大于pivot的元素移动至其右侧，当全部移动完成时，左右指针会正好相遇在pivot元素上 不难想到，当获得了pivot的索引值index，就可以直接检查index是否正好等于k-1（假设k指第k小的元素值），如果相等，则说明这个pivot就是要找的第k小的元素；如果不等，则进一步检查index与k-1之间的大小关系并确定新pivot： 如果index > k-1，说明要寻找的元素相较于pivot来说更小，那么去小于pivot的区域再找 如果index < k-1，说明要寻找的元素相较于pivot来说更大，那么去大于pivot的区域再找 以上过程完全可以用递归来实现（事实上这也是快速排序所进行的过程），而在区域中选取pivot实际上是随机取得的。另外，当传入的左右限制left == right时，说明此区域仅有一个元素，需要寻找的只能是该元素，直接返回nums[left]即可 代码实现（Java） 类的总体结构应为： import java.util.Random; class Find { private int[] nums; private int k; public Find(int[] nums) {...} public int getKElement(int k) {...} private int randomSelect(int left, int right) {...} // 递归部分，选取随机数、划分后判断 private int partition(int random, int p, int q) {...} // 划分部分 private void swap(int i, int j) {...} // 用于交换数组元素的工具方法 } 先编写划分部分的方法，输入数组、随机索引值、左右限制，输出划分后pivot的索引值： public int partition(int random, int p, int q) { while (p != q) { int pivot = nums[random]; while (pivot > nums[p]) p++; swap(nums, p, random); random = p; while (pivot < nums[q]) q--; swap(nums, q, random); random = q; } return random; } 编写递归部分： ...

Stream在数组处理上的特点 首先明确一点： char[] chs = {'h','e','l','l','o'}; int[] ints = {1,2,3,4}; String str = "hello"; String[] strs = {"hello","world"}; //数组的Stream流泛型都是数组，而不是数组中的单个元素 Stream<char[]> chsStream = Stream.of(chs); Stream<int[]> intsStream = Stream.of(ints); //String的Stream流泛型都是String Stream<String> strStream = Stream.of(str); Stream<String> strsStream = Stream.of(strs); //在这种情况下，流中的每个元素都是String[]数组中的单个元素 如果我们的目的是处理数组中的每一个元素，那么对于Stream<T[]>这种类型的流我们一般是并不想见到的 解决方法就是使用基本类型流，即IntStream、DoubleStream和LongStream，然后再操作（或对基本类型流先进行boxed()转为Stream<T>再操作），而得到基本类型流的方法有两种： Arrays.stream() 基本类型流名.of() Stream处理字符串 - 以凯撒密码为例 若要对字符串中的每个字符进行逐个操作，最容易想到，也最快的方法就是先使用toCharArray()将字符串转为一个char[]数组，再使用循环进行操作，最后使用String的构造方法将之再转换回字符串： //正常方法 char[] chars = str.toCharArray(); for(int i=0;i< chars.length;i++) { chars[i] = (char)((chars[i]-'a'+k)%26+'a'); } System.out.println(new String(chars)); 这次我舍近求远，想用Stream流来模拟生成凯撒密码密文的操作 根据Stream处理数组的特点，String转换成char[]之后，要想对数组的每个元素都进行操作，就要使用基本类型流，但并没有char类型的基本类型流，在这就导致我只能得到Stream<char[]>，而得不到如CharStream或是Stream<Character>的流 所以，不能将String转为char[]数组 那么，借助String[]数组的流中可以遍历到数组中的每个元素的特点，考虑将String转为String[]数组，再使用map()将每个元素转换成char，这样才得到一个Stream<Character>： Stream<String> t = Stream.of(str.split("")); //str:{"h","e","l","l","o"} Stream<Character> chStream = t.map(s -> s.charAt(0)); chStream = t.map(ch -> (char)((ch-'a'+1)%26+'a'); /* * 也可直接一步完成操作： * s -> (char)((s.charAt(0)-'a'+1)%26+'a') */ 得到了Stream<Character>以后，才能正式地开始遍历每个字符并处理。处理结束后，将Stream<Character>重新拼接成字符串即可 ...

考虑一个数组： int[] nums = {9,6,5,7,4,8,3,1,2}; 对于数组，列举几个转换Stream流的操作及返回值： //返回Stream对象，但泛型为int[]数组 Stream<int[]> nums1 = Stream.of(nums); //返回一个IntStream对象，默认无泛型 IntStream nums2 = IntStream.of(nums); IntStream nums3 = Arrays.stream(nums); 若想要对数组进行排序，则使用sorted()方法，但需要注意的是，IntStream的sorted无入参，即只能自然排序，只有Stream中的sorted才能指定比较器，所以将之转化为Stream类型，再进行排序： //使用boxed()将IntStream转换为Stream类型，即将IntStream中的每个整型都进行装箱 //nums2同理 Stream<Integer> boxedNums = nums3.boxed(); //进行排序 Stream<Integer> sortedNums = boxedNums.sorted((o1,o2) -> o2-o1); 排序完成后，仍是一个Stream对象。若想将之转换回数组，则使用toArray()方法 但仍然需要注意，在Stream中，由于Stream的泛用性，toArray()返回的是Object类型的数组，而非int类型，所以，需要首先转化为IntStream，表示其中存储的都是整型数据，然后使用该对象中的toArray()方法： //使用mapToInt转化为IntStream对象 //此处的intValue是将原本的Integer包装类转换为int基本类 IntStream temp = sortedNums.mapToInt(Integer::intValue); //最终转换为数组 int[] res = temp.toArray(); 以下总结前文提到的Stream和IntStream的同名方法及必要说明，方便判断是否需要进行对象类型的转换： Stream: Stream<T> of(T t)：返回一个Stream对象，其泛型是参数泛型 Stream sorted()：可带参可不带参 Object[] toArray()：返回一个Obj的数组 IntStream： IntStream of(int… values)：返回一个IntStream对象，直接存有数组每个元素 IntStream sorted()：只有无参的 int[] toArray()：返回一个int的数组 此外，Arrays.stream()也能返回一个IntStream对象，效果与IntStream.of()一致，且其针对数据数组有更多重载，泛用性更强