Java实现的计算最大下标距离算法示例

本文实例讲述了Java实现的计算最大下标距离算法。分享给大家供大家参考，具体如下：

题目描述

给定一个整形数组，找出最大下标距离j−i, 当且A[i] < A[j] 和 i < j

解法

复杂度：三次扫描，每次的复杂度O(N)
算法：{5,3,4,0,1,4,1}
找出从第一个元素开始的下降序列{5,3,0}
i=3,j=6, j从尾部扫描
初始化，i=3, j=6, A[i]=0

实现代码

public static int maxindexdistance(int A[]) {
    boolean[] isDes = new boolean[A.length];
    int min = A[0];
    isDes[0] = true;
    for (int i = 0; i < A.length; i++) {
      if (A[i] < min) {
        isDes[i] = true;
        min = A[i];
      }
    }
    int maxdis = 0;
    int i = A.length - 1;
    int j = A.length - 1;
    System.out.println(Arrays.toString(isDes));
    while (i >= 0) {
      while (isDes[i] == false) {
        i--;
      }
      while (j > i && A[j] <= A[i]) {
        j--;
      }
      if ((j - i) > maxdis) {
        maxdis = j - i;
      }
      i--;
    }
    return maxdis;
}

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

您可能感兴趣的文章:

  • java图像处理之倒角距离变换
  • Java动态规划之编辑距离问题示例代码
  • 利用java、js或mysql计算高德地图中两坐标之间的距离
  • Java实现控制台输出两点间距离
  • Java编程获取经纬度之间距离的方法
  • java实现计算地理坐标之间的距离
  • java计算两点间的距离方法总结
赞 (0)

相关推荐

  • Java动态规划之编辑距离问题示例代码

    Java动态规划之编辑距离问题示例代码

    动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移.一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划. 动态规划实际上是一类题目的总称,并不是指某个固定的算法.动态规划的意义就是通过采用递推(或者分而治之)的策略,通过解决大问题的子问题从而解决整体的做法.动态规划的核心思想是巧妙的将问题拆分成多个子问题,通过计算子问题而得到整体问题的解.而子问题又可以拆分成更多的子问题,从而用类似递推迭代的方法解决要求的问题.问题描述: 对于序列S和T,

  • java图像处理之倒角距离变换

    java图像处理之倒角距离变换

    图像处理中的倒角距离变换(Chamfer Distance Transform)在对象匹配识别中经常用到,算法基本上是基于3x3的窗口来生成每个像素的距离值,分为两步完成距离变换,第一步从左上角开始,从左向右.从上到下移动窗口扫描每个像素,检测在中心像素x的周围0.1.2.3四个像素,保存最小距离与位置作为结果,图示如下: 第二步从底向上.从右向左,对每个像素,检测相邻像素4.5.6.7保存最小距离与位置作为结果,如图示所: 完成这两步以后,得到的结果输出即为倒角距离变换的结果.完整的图像倒角距

  • Java实现控制台输出两点间距离

    计算两点之间的距离然后在控制台输出,这个题目还是挺简单的.下面我们来看看具体代码. package com.swift; import java.util.Scanner; public class PToP { public static void main(String[] args) { Scanner scan=new Scanner(System.in); System.out.println("请输入第一个点的坐标值x1"); Double x1=Double.parseD

  • 利用java、js或mysql计算高德地图中两坐标之间的距离

    利用java、js或mysql计算高德地图中两坐标之间的距离

    前言 因为工作的原因,最近在做与地图相关的应用,使用了高德地图,研究了下高德地图计算两坐标距离的方法,官网上提供的开发包中有相关的方法,但是我的产品中比较特殊,无法直接使用提供的方法,所以就自己封装了相关计算方法,供大家参考,下面话不多说了,来一起看看详细的介绍吧. Java实现 首先定义一个用于存储经纬度的类,这里起个名字叫:LngLat package amap; import java.text.DecimalFormat; import java.text.DecimalFormatSy

  • java实现计算地理坐标之间的距离

    java实现计算两经纬度点之间的距离,直接上代码,具体解释请参考注释 复制代码 代码如下: package com.jttx.poi.utils; import com.jttx.poi.entity.Point; /**  * Created by louis on 2014/9/2.  */ public class GeoUtils {     /**      * 计算两经纬度点之间的距离(单位:米)      * @param lng1  经度      * @param lat1 

  • java计算两点间的距离方法总结

    使用java自带的Point类 import java.awt.Point;//引用awt包下的Point类,此类的功能是表示 (x,y) 坐标空间中的位置的点 public class Distance { public static void main(String[] args) { Point p1 = new Point(5, 6);// 定义第一个点的坐标(5,6) Point p2 = new Point(7,8);// 定义第二个点的坐标(7,8) //定位坐标 System.o

  • Java编程获取经纬度之间距离的方法

    本文实例讲述了Java编程获取经纬度之间距离的方法.分享给大家供大家参考,具体如下: public class GeoUtil { /** * 根据经纬度和距离返回一个矩形范围 * * @param lng * 经度 * @param lat * 纬度 * @param distance * 距离(单位为米) * @return [lng1,lat1, lng2,lat2] 矩形的左下角(lng1,lat1)和右上角(lng2,lat2) */ public static double[] ge

  • Java实现的计算最大下标距离算法示例

    本文实例讲述了Java实现的计算最大下标距离算法.分享给大家供大家参考,具体如下: 题目描述 给定一个整形数组,找出最大下标距离j−i, 当且A[i] < A[j] 和 i < j 解法 复杂度:三次扫描,每次的复杂度O(N) 算法:{5,3,4,0,1,4,1} 找出从第一个元素开始的下降序列{5,3,0} i=3,j=6, j从尾部扫描 初始化,i=3, j=6, A[i]=0 实现代码 public static int maxindexdistance(int A[]) { boole

  • Python实现的计算马氏距离算法示例

    Python实现的计算马氏距离算法示例

    本文实例讲述了Python实现的计算马氏距离算法.分享给大家供大家参考,具体如下: 我给写成函数调用了 python实现马氏距离源代码: # encoding: utf-8 from __future__ import division import sys reload(sys) sys.setdefaultencoding('utf-8') import numpy as np def mashi_distance(x,y): print x print y #马氏距离要求样本数要大于维数,

  • Java实现合并两个有序序列算法示例

    本文实例讲述了Java实现合并两个有序序列算法.分享给大家供大家参考,具体如下: 问题描述 输入:序列A<a0,a1,a2,...aq,aq+1,aq+2,...,ar>,其中a0<a1<...<aq,aq+1<aq+2<...<ar 输出:序列B<b0,b1,...,br>,其中b0<b1<...<br 算法思想 创建一个长度为r的数组R,将A中的序列看作是两个有序序列 B=A<a0,a1,a2,...,aq> C

  • 基于Java实现的一层简单人工神经网络算法示例

    基于Java实现的一层简单人工神经网络算法示例

    本文实例讲述了基于Java实现的一层简单人工神经网络算法.分享给大家供大家参考,具体如下: 先来看看笔者绘制的算法图: 2.数据类 import java.util.Arrays; public class Data { double[] vector; int dimention; int type; public double[] getVector() { return vector; } public void setVector(double[] vector) { this.vect

  • Java基于分治法实现的快速排序算法示例

    Java基于分治法实现的快速排序算法示例

    本文实例讲述了Java基于分治法实现的快速排序算法.分享给大家供大家参考,具体如下: package cn.nwsuaf.quick; /** * 随机产生20个数,并对其进行快速排序 * * @author 刘永浪 * */ public class Quick { /** * 交换函数,实现数组中两个数的交换操作 * * @param array * 待操作数组 * @param i * 交换数组的第一个下标 * @param j * 交换数组的第二个下标 */ public static

  • Java实现的计算稀疏矩阵余弦相似度示例

    本文实例讲述了Java实现的计算稀疏矩阵余弦相似度功能.分享给大家供大家参考,具体如下: import java.util.HashMap; public class MyUDF{ /** * UDF Evaluate接口 * * UDF在记录层面上是一对一,字段上是一对一或多对一. Evaluate方法在每条记录上被调用一次,输入为一个或多个字段,输出为一个字段 */ public Double evaluate(String a, String b) { // TODO: 请按需要修改参数和

  • Java实现求数组最长子序列算法示例

    本文实例讲述了Java实现求数组最长子序列算法.分享给大家供大家参考,具体如下: 问题:给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱) 例如:给定一个长度为8的数组A{1,3,5,2,4,6,7,8},则其最长的单调递增子序列为{1,2,4,6,7,8},长度为6. 思路1:第一眼看到题目,很多人肯定第一时间想到的是LCS.先给数组排个序形成新数组,然后再把新数组和原数组拿来求LCS,即可得到答案.这种解法很多人能想得到,所以就不再赘述. 思路2:按照思路1的

  • java实现的AES秘钥生成算法示例

    本文实例讲述了java实现的AES秘钥生成算法.分享给大家供大家参考,具体如下: import java.security.NoSuchAlgorithmException; import java.security.SecureRandom; import javax.crypto.KeyGenerator; import javax.crypto.SecretKey; public class Test { public static void main(String[] args) { g

  • PHP数据分析引擎计算余弦相似度算法示例

    本文实例讲述了PHP数据分析引擎计算余弦相似度算法.分享给大家供大家参考,具体如下: 关于余弦相似度的相关介绍可参考百度百科:余弦相似度 <?php /** * 数据分析引擎 * 分析向量的元素 必须和基准向量的元素一致,取最大个数,分析向量不足元素以0填补. * 求出分析向量与基准向量的余弦值 * @author yu.guo@okhqb.com */ /** * 获得向量的模 * @param unknown_type $array 传入分析数据的基准点的N维向量.|eg:array(1,1

  • Java实现的猴子吃桃问题算法示例

    本文实例讲述了Java实现的猴子吃桃问题算法.分享给大家供大家参考,具体如下: 猴子吃桃问题 概述:猴子第一天摘下N个桃子,当时就吃了一半,还不过瘾,就又吃了一个:第二天又将剩下的桃子吃掉了一半,又多吃了一个:以后每天都吃前一天身下的一半零一个,到第n天再想吃的时候就只剩下一个桃子了,求第一天共摘了多少个桃子? 思路及演算步骤(求出共摘多少桃子的函数表达式): 离现在的天数作为变量 f(1) = 1 (剩下桃子的数目) f(2) = f(3) - (吃掉了一些) =   f(3) -(f(3)/

随机推荐