每日算法之数组中的逆序对
2023-03-31 10:41:10 时间
JZ51 数组中的逆序对
题目
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
方法1:暴力
思路
算法实现
两个for循环,如果前面的数大于后面的计数加1即可
问题
当输入数过大时,需要的时间会很长,所以此方法不行
代码
package mid.JZ51数组中的逆序对;
import java.util.ArrayList;
public class Solution {
public int InversePairs1(int[] array) {
int k = 1000000007;
if (array.length <= 1) return 0;
int res = 0;
for (int i = 1; i < array.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (array[i] < array[j])
res++;
}
}
return res % k;
}
}
方法2 归并排序思想
思路
- 先分:分呢,就是将数组分为两个子数组,两个子数组分为四个子数组,依次向下分,直到数组不能再分为止!
- 后并:并呢,就是从最小的数组按照顺序合并,从小到大或从大到小,依次向上合并,最后得到合并完的顺序数组!
- 归并统计法,关键点在于合并环节,在合并数组的时候,当发现右边的小于左边的时候,此时可以直接求出当前产生的逆序对的个数。
代码
package mid.JZ51数组中的逆序对;
import java.util.Arrays;
public class Solution {
/**
* 分治
*
* @param array
* @return
*/
public int count = 0;
public int InversePairs(int[] array) {
divMerge(array, 0, array.length-1);
return count;
}
public void divMerge(int[] array, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
//分左边
divMerge(array, left, mid);
//分右边
divMerge(array, mid + 1, right);
//合并
int i = left;
int j = mid + 1;
//临时数组
int[] tmp = new int[right - left + 1];
int k = 0;
while (i <= mid && j <= right) {
if (array[i] > array[j]) {
tmp[k++] = array[j++];
count += mid - i + 1;
count %= 1000000007;
} else {
tmp[k++] = array[i++];
}
}
while (i <= mid) {
// 如果右边的走完了 就把左边的放到tmp后面
tmp[k++] = array[i++];
}
while (j <= right) {
// 如果左边的走完了 就把右边的放到tmp后面
tmp[k++] = array[j++];
}
// 把排好序的tmp 移到 array中
for(int l=0; l<k; l++) {
array[left++] = tmp[l];
}
}
public static void main(String[] args) {
System.out.println(new Solution().InversePairs(new int[]{1, 2, 3, 4, 5, 6, 7, 0}));
}
/**
* 暴力
*
* @param array
* @return
*/
public int InversePairs1(int[] array) {
int k = 1000000007;
if (array.length <= 1) return 0;
int res = 0;
for (int i = 1; i < array.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (array[i] < array[j])
res++;
}
}
return res % k;
}
}
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十