排序
把数组排成最小的数
题目链接
import java.util.*; public class Solution { public String PrintMinNumber(int [] numbers) { //空数组的情况 if(numbers == null || numbers.length == 0) return ""; String[] nums = new String[numbers.length]; //将数字转成字符 for(int i = 0; i < numbers.length; i++) nums[i] = numbers[i]+""; //按照重载排序 Arrays.sort(nums, new Comparator<String>() { public int compare(String s1, String s2) { return (s1 + s2).compareTo(s2 + s1); } }); StringBuilder res = new StringBuilder(); //字符串叠加 for(int i = 0; i < nums.length; i++) res.append(nums[i]); return res.toString(); } }
这里题目重点就是自己设计一个排序,通过Comparator接口!
字符串拼接s1 + s21>s2 + s1说明s1和s2位置需要交换!
相似题目:数据流中的中位数
读懂题意!
import java.util.*; public class Solution { //将数据流保存在table中! private ArrayList<Integer> table = new ArrayList<>(); public void Insert(Integer num) { //在table数据流中插入num值! if(table.isEmpty()){ //直接尾插 table.add(num); }else{ //不为空,找到合适位置插入!升序排序! int i = 0; for(i = 0;i< table.size();i++){ if(table.get(i)>num){ //找到了合适位置! table.add(i,num); break; } } if(i==table.size()){ //尾插! table.add(i,num); } } } public Double GetMedian() { //计算中位数! if(table.isEmpty()){ return 0.0; }else{ int size = table.size(); if(size%2==0){ //偶数! return (double)(table.get(size/2)+table.get(size/2-1))/2; }else{ //奇数 return (double)table.get(size/2); } } } }
插入考虑边界问题!
数组中的逆序对(归并统计法)
题目链接
public class Solution { private int sum = 0;//保存结果值! public int InversePairs(int [] array) { //归并统计法! //采用归并排序的思想,在毕竟合并时统计逆序对的组数! if(array.length<2){ //无逆序队 return 0; } //进行归并统计! mergeSort(array,0,array.length-1); return sum; } public void mergeSort(int[] array,int left,int right){ //进行先分! int mid = left + (right-left)/2; if(left<right){ //左区间! mergeSort(array,left,mid); //右区间! mergeSort(array,mid+1,right); //后和并 merge(array,left,mid,right); } } public void merge(int[] array,int left,int mid,int right){ //我们进行合并时需要有个临时数组保存 int[] tmp = new int[right-left+1]; //记录临时数组开始下标位置! int tmpIndex = 0; //记录原数组开始下标位置(临时数组数据需要放入到原数组中) int arrayIndex = left; //左区间开始位置! int l = left; //右区间开始位置! int r = mid+1; //进行比较合并! while(l<=mid&&r<=right){ if(array[l]<=array[r]){ //无逆序,直接将l下标保存在临时数组! tmp[tmpIndex++] = array[l++]; }else{ //逆序,交换(就将r下标位置保存) tmp[tmpIndex++] = array[r++]; //记录逆序对数! //进行归并时,左右数组已经分别有序! //l大于r下标元素,也就是l到mid区间都大于r下标元素 //所以逆序对数为 l下标位置到 r位置个数! sum += mid - l +1; sum %= 1000000007; } } //区间长度不相等,有剩余值! while(l<=mid){ tmp[tmpIndex++] = array[l++]; } while(r<=right){ tmp[tmpIndex++] = array[r++]; } //将元素放回到原数组! for(int x : tmp){ array[arrayIndex++] = x; } } }
数字在升序数组中出现的次数
题目链接
public class Solution { public int GetNumberOfK(int [] array , int k) { //数组以有序! //二分查找! int l = 0,r = array.length-1; int mid = l + (r-l)/2; boolean flg = false; while(l<=r){ mid = l + (r-l)/2; if(array[mid]>k){ //定位在左区间! r = mid-1; }else if(array[mid]<k){ //定位在右区间! l = mid+1; }else{ //相等! //找到! flg = true; break; } } if(flg){ for(int i = l;i<=mid;i++){ if(array[i]==k){ //相等区间左边界! l = i; break; } } for(int i = r;i>=mid;i--){ if(array[i]==k){ //相等区间右边界! r = i; break; } } return r - l +1; } return 0; } }
public class Solution { public int GetNumberOfK(int [] array , int k) { //直接找到边界,[left,right) 左闭右开! return bisearch(array,k+0.5) - bisearch(array,k-0.5); } public int bisearch(int[] array,double k){ int left = 0,right = array.length-1; while(left<=right){ int mid = left + (right-left)/2; if(array[mid]<k){ left = mid + 1; }else{ right = mid - 1; } } //这里二分如果没找到返回的是大于该值的一个下标 return left; } }
丑数
链接
解题思路：
我们先看到题目，把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。
有了上面的定义我们就可以知道，丑数的形式就是2x3y5^z
所以我们可以定义一个数组res，存储第n个丑数。
因为我们要将丑数按从小到大的顺序排序，所以我们就得将对应的丑数放在对应的下标位置，小的放前面。
因为最小的丑数就是1，所以我们初始化res[0]=1，那么接下来的一个丑数是什么呢？我们自己知道是2。
但是我们能不能有一个格式，去将得到接下来的丑数是谁呢？
这个时候上面我们的出来的丑数的格式就起作用了，丑数的形式无非就是这样2x3y5z
所以我们就将res[n]去乘以 2、3、5，然后比较出最小的那个，就是我们当前的下一个丑数了。
public class Solution { public int GetUglyNumber_Solution(int index) { if(index==0){ return 0; } //利用 丑数: 2^x*3^y*5^z! int[] arr = new int[index];//保存前index丑数值! arr[0] = 1; int i2 = 0,i3 = 0,i5 = 0;//记录2/3/5分别相乘的次数! for(int i = 1;i<index;i++){ //将3个中最小丑数放在前面! //每次都是求出最小的丑数! arr[i] = Math.min(arr[i2]*2,Math.min(arr[i3]*3,arr[i5]*5)); if(arr[i]==arr[i2]*2){ //说明这里的 2 相乘次数加一! i2++; } if(arr[i]==arr[i3]*3){ //说明这里的 3 相乘次数加一! i3++; } if(arr[i]==arr[i5]*5){ //说明这里的 5 相乘次数加一! i5++; } } return arr[index-1]; } }
