Java实现中值问题
JAVA 实现 问题
2023-09-14 08:58:13 时间
中值问题是求一个n个数列表中某一数组下标k,它要求该下标元素比列表中的一半元素大,又比另一半元素小,这个中间的值被称为中值。
使用Lomuto划分算法思想,此处引用《算法设计与分析基础》第三版上一段文字介绍及配图,具体如下:
package com.liuzhen.chapter4;
public class MedianProblem {
//Lomuto划分
/*
* 参数A:给定的随机数数组
* 参数start:开始进行选择的数组元素位置
* 参数end:最后一个进行选择的数组元素位置
* 函数功能:返回A[start]到A[end]元素中间的某一元素位置result,使得 左边部分元素 < A[result] <=右边部分元素
*/
public int LomutoPartition(int[] A,int start,int end){
int begin = A[start];
int result = start;
for(int i = start+1;i <= end;i++){
if(A[i] < begin){
/*
* 一旦出现小于begin的元素,result向后移动一位;
* 出现大于的不移动,当再次出现小于begin的元素,result向后移动一位,
* 此时result恰好指向第一个大于begin的元素,此时执行swap(A,result,i)
*/
result = result + 1;
swap(A,result,i);
}
}
swap(A,start,result);
return result;
}
//交换数组中位置为m和n上的元素值
public void swap(int[] A,int m,int n){
int temp = A[m];
A[m] = A[n];
A[n] = temp;
}
public static void main(String[] args){
MedianProblem test = new MedianProblem();
int[] A = {4,1,10,8,7,12,9,2,15};
int result = test.LomutoPartition(A, 0, A.length-1);
System.out.println("对数组进栈Lomuto划分后结果:");
for(int i = 0;i < A.length;i++)
System.out.print(A[i]+" ");
System.out.println("\n"+"进行Lomuto划分后的数组中轴位置:"+result);
}
}
运行结果:
对数组进栈Lomuto划分后结果:
2 1 4 8 7 12 9 10 15
进行Lomuto划分后的数组中轴位置:2
相关文章
- Java实现 LeetCode 761 特殊的二进制序列(括号问题)
- Java实现 LeetCode 744 寻找比目标字母大的最小字母(二分法)
- Java实现 LeetCode 726 原子的数量(递归+HashMap处理)
- Java实现 LeetCode 721 账户合并(并查集)
- Java实现 LeetCode 605 种花问题(边界问题)
- Java实现 LeetCode 455 分发饼干
- Java实现 LeetCode 51 N皇后
- Java实现 洛谷 P1618 三连击(升级版)
- java实现洛谷P3376【模板】网络最大流
- java实现低碳生活大奖赛
- java实现第五届蓝桥杯猜字母
- java实现第六届蓝桥杯九数组分数
- Java实现第八届蓝桥杯日期问题
- Java实现第九届蓝桥杯螺旋折线
- Java实现找零问题
- Java实现选择问题
- Java实现子序列问题
- Java实现 蓝桥杯VIP 算法提高 传染病控制
- Java实现 蓝桥杯VIP 算法提高 铺地毯
- Java实现 蓝桥杯VIP 算法训练 暗恋
- Java 蓝桥杯 算法训练 字符串的展开 (JAVA语言实现)
- Java 蓝桥杯 算法训练 字符串的展开 (JAVA语言实现)
- 【JAVA】 04-Java中的多线程
- Atitit.java eval功能的实现 Compiler API
- 基于JAVA实现的WEB端UI自动化 - WebDriver框架篇 - ant使用 - ant调用testng文件及ant 调用testng遇到的问题