1、数组中的逆序对
（学习视频推荐：java课程）
【题目】
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数 P。并将 P 对 1000000007 取模的结果输出。 即输出 P%1000000007
立即学习“Java免费学习笔记（深入）”；
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4对于%75的数据,size<=10^5对于%100的数据,size<=2*10^5
代码：
/** *在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。 * 输入一个数组，求出这个数组中的逆序对的总数 P。 * 并将 P 对 1000000007 取模的结果输出。 即输出 P%1000000007 * * 利用归并排序的思想(倒序) * 当得到left和right两个待归并的数组时，由于二者已经排好顺序 * 当left中的A元素大于right中的B元素， * 那么right.length-b_index 个逆序对 * */ int count; public int InversePairs(int [] array) { return Merge(array,0,array.length-1); } public int Merge(int[] a, int start, int end) { if (start >= end) return count; int i,j,mid,index; int[] temp; mid = (start + end) / 2; Merge(a,start,mid); Merge(a,mid+1,end); i = start; j = mid + 1; temp = new int[end-start+1]; index = 0; while (i<=mid && j a[j]) { count = (count +end - j + 1) % 1000000007; temp[index++] = a[i++]; } else { temp[index++] = a[j++]; } } while (i<=mid) temp[index++] = a[i++]; while (j<=end) temp[index++] = a[j++]; index = start; for (i=0;i<temp.length; i++) { a[index++] = temp[i]; } return count; }
【思考】
在归并排序的过程中 后一个数组的数如小于前一个数组的数，则一定能够构成逆序对且逆序对的数目可计算，因为待归并的两个数组提前已经归并排序过，所以不会出现像前面那样少统计或者多统计的情况出现。
[A，B] 中的逆序对 =[A] 的逆序对 +[B] 中的逆序对 + 将 A，B 混排在一起的逆序对
注意：题目中有一个特殊要求，需要取模，这个取模不仅仅在结果取模，还需要在过程计算中取模。
2、数组中只出现一次的数字
【题目】
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
【代码】
/** * 一个整型数组里除了两个数字之外，其他的数字都出现了两次。 * 请写程序找出这两个只出现一次的数字。 * * 位运算中异或的性质： * 两个相同数字异或 = 0，一个数和 0 异或还是它本身。 * a ⊕ a = 0 * a ⊕ b ⊕ a = b. * a ⊕ 0 = a * * 当只有一个数出现一次时，我们把数组中所有的数，依次异或运算， * 最后剩下的就是落单的数，因为成对儿出现的都抵消了。 * * 当出现两个数只出现一次时，依旧是依次异或运算， * 剩下的结果是两个只出现一次的数的异或结果 * 因为这两个数不同，所以我们通过二进制的异或把二者分开，在依次异或即可分别得到 * */ public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { int i,n,res,count,res1,res2; n = array.length; if (n == 0 || array == null) return; res = 0;// 记录两个不同的数的异或结果 for (i=0; i<n; i++) { res = res ^ array[i]; } // 找到异或结果的二进制的的从右向左的第一个1 count = 1; while ((count & res) == 0) count = count << 1; // 通过找到的二进制结果来区分两个只出现第一次的数 res1 = 0; res2 = 0; for (i=0; i<n; i++) { if ((count & array[i]) == 0) { res1 = res1 ^ array[i]; } else { res2 = res2 ^ array[i]; } } num1[0] = res1; num2[0] = res2; }
【思考】
首先：位运算中异或的性质：两个相同数字异或 = 0，一个数和 0 异或还是它本身。
当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。
依照这个思路，我们来看两个数（我们假设是 AB）出现一次的数组。我们首先还是先异或，剩下的数字肯定是 A、B 异或的结果，这个结果的二进制中的 1，表现的是 A 和 B 的不同的位。我们就取第一个 1 所在的位数，假设是第 3 位，接着把原数组分成两组，分组标准是第 3 位是否为 1。如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。
（更多相关面试题推荐：java面试题及答案）
3、和为 S 的两个数字
白瓜面试
白瓜面试 – AI面试助手,辅助笔试面试神器
40 查看详情 
【题目】
输入一个递增排序的数组和一个数字 S，在数组中查找两个数，使得他们的和正好是 S，如果有多对数字的和等于 S，输出两个数的乘积最小的。
对应每个测试案例，输出两个数，小的先输出。
【代码】
/** * 输入一个递增排序的数组和一个数字 S， * 在数组中查找两个数，使得他们的和正好是 S， * 如果有多对数字的和等于 S，输出两个数的乘积最小的。 * */ public ArrayList FindNumbersWithSum(int [] array, int sum) { int mid,i,index,n,j; ArrayList list; n = array.length; if (n == 0 || array == null || sum == 0) return new ArrayList(); mid = sum >> 1; if (array[0] > mid) return new ArrayList(); // 前两个元素和为sum list = new ArrayList(); if (array[0] == mid) { if (array[0] + array[1] == sum) { list.add(array[0]); list.add(array[1]); } return list; } // 获得mid在array的索引 index = 0; for (i=0; i= mid) { index = i; break; } } i = 0; j = index + 1; while (i<=index) { while (array[i] + array[j] < sum) { j++; } if (array[i] + array[j] == sum) { list.add(array[i]); list.add(array[j]); break; } else { i++; j = index + 1; } } return list; }
4、和为 S 的连续正数序列
【题目】
小明很喜欢数学，有一天他在做数学作业时，要求计算出 9~16 的和，他马上就写出了正确答案是 100。但是他并不满足于此，他在想究竟有多少种连续的正数序列的和为 100 (至少包括两个数)。没多久，他就得到另一组连续正数和为 100 的序列：18,19,20,21,22。现在把问题交给你，你能不能也很快的找出所有和为 S 的连续正数序列？Good Luck!
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
【代码】
/** * 输出所有和为S的连续正数序列。 * 序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序 * * 思路：回溯 * 算子，paths，path * */ TreeSet path; ArrayList<ArrayList> paths; ArrayList list; public ArrayList<ArrayList> FindContinuousSequence(int sum) { if (sum < 3) return new ArrayList(); int n,i,j,mid,count; paths = new ArrayList(); if (sum == 3) { list = new ArrayList(); list.add(1); list.add(2); paths.add(list); return paths; } // n代表sum这个数最多由几个数字构成 n = (int)Math.sqrt(sum) + 1; for (i=n; i>=2; i--) { count = 0; mid = sum / i; count += mid; path = new TreeSet(); path.add(mid); j = 1; while (count < sum) { count += mid+j; path.add(mid+j); count += mid-j; path.add(mid-j); j++; } if (count == sum) { list = new ArrayList(); list.addAll(path); paths.add(list); } else { int last = path.last(); int first = path.first(); if (count-last == sum) { path.remove(last); list = new ArrayList(); list.addAll(path); paths.add(list); } if (count-first == sum) { path.remove(first); list = new ArrayList(); list.addAll(path); paths.add(list); } } } return paths; }
【思路】
双指针法
左右指针不断圈定连续序列的范围
输入sum=20（1，2，3，4，5，6，7，8，9，10，11，12，13，14，15
1，定义两个指针，左指针从1开始，右指针从2开始
循环开始
2，求和（1+2 = 3
3，如果判断3小于20，右指针++，2变为3，求和3+3=6。循环一直到右指针=6，和为21。
4，else if 判断21大于20，左指针++，1变为2，和减去左指针值，和为21-1=20。
5，else 和与输入一样，存数。 【再把右指针++，求和，求剩余组合】
循环结束
5、扑克牌顺子
【题目】
LL 今天心情特别好，因为他去买了一副扑克牌，发现里面居然有 2 个大王，2 个小王 (一副牌原本是 54 张 _)… 他随机从中抽出了 5 张牌，想测测自己的手气，看看能不能抽到顺子，如果抽到的话，他决定去买体育彩票，嘿嘿！！“红心 A, 黑桃 3, 小王，大王，方片 5”,“Oh My God!” 不是顺子…LL 不高兴了，他想了想，决定大 小 王可以看成任何数字，并且 A 看作 1,J 为 11,Q 为 12,K 为 13。上面的 5 张牌就可以变成 “1,2,3,4,5”(大小王分别看作 2 和 4),“So Lucky!”。LL 决定去买体育彩票啦。 现在，要求你使用这幅牌模拟上面的过程，然后告诉我们 LL 的运气如何， 如果牌能组成顺子就输出 true，否则就输出 false。为了方便起见，你可以认为大小王是 0。
【代码】
/** * 判断顺子，大小王为0 * * 计算0的个数 * 计算非0的差 * */ public boolean isContinuous(int [] numbers) { if (numbers.length == 0 || numbers == null) return false; Arrays.sort(numbers); int n,i,count,minus; n = numbers.length; count = 0; minus = 0; for (i=0; i count ? false : true; }
【思考】
可以考虑使用treeset这个结构，本身带有排序功能，并且不会存储相同元素，可以方便判断。
相关推荐：java入门
以上就是java面试中常见的数组题目汇总（四）的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/569832.html
微信扫一扫 
支付宝扫一扫 
