精华内容
下载资源
问答
  • 寻找数组元素中最值的方法

    思路:

    假设第一个元素的值最大;

    用第二个和第一个比较,如果第二个大,说明第二个是已知最大值;

    用第三个和已知最大的比,如果第三个大,说明第三个是已知最大的;

    以此类推,直到所有元素都比较完。

    同理可求最小值

    示例:

    public class MaxOfArray {
    	public static void main(String[] args) {
    		//声明数组
    		int[] arr = new int[10];
    		//给数组元素随机赋值
    		for(int index = 0; index < arr.length; index++) {
    			arr[index] = (int)(Math.random() * 100);
    		}
    		//遍历输出数组元素
    		for(int index = 0; index < arr.length; index++) {
    			System.out.print(arr[index] + "\t");
    		}
    		System.out.println();
    		
    		//==============寻找最大值
    		//假设最大值是第一个元素
    		int max = arr[0];
    		//遍历
    		for(int index = 1; index < arr.length; index++) {
    			//如果遍历得到的元素比max大,就赋值给max
    			if(max < arr[index]) {
    				max = arr[index];
    			}
    		}
    		//输出max
    		System.out.println(max);
    	}
    
    }

     

    展开全文
  • 主要介绍了Go语言算法之寻找数组第二大元素的方法,以实例形式分析了不排序、只循环一次来实现寻找数组第二大元素的技巧,是比较典型的算法,需要的朋友可以参考下
  • 寻找数组中第二大的数字 解题思路: 先定义两个变量:一个变量用来存储数组的最大数,初始为数组第一个数,另外一个变量存储数组元素第二大数字,初始为最小负整数,遍历数组并进行判断。 代码展示 public ...

    寻找数组中第二大的数字

    解题思路:
    先定义两个变量:一个变量用来存储数组的最大数,初始值为数组第一个数,另外一个变量存储数组元素的第二大数字,初始值为最小负整数,遍历数组并进行判断。

    代码展示

    public static void main(String[] args) {
    	// TODO Auto-generated method stub
    	int[] array = {7,3,19,40,4,7,1};
    	System.out.println("第二大数为:"+FindSecMax(array));
    }
    
    private static int FindSecMax(int[] data) {
    	// TODO Auto-generated method stub
    	int max_Number=data[0];	//	最大数
    	int sec_Number=Integer.MIN_VALUE;	//	第二大数
    	for(int i=1;i<data.length;i++) {
    		if(data[i]>max_Number) {
    			//	进行交换
    			sec_Number = max_Number;
    			max_Number=data[i];
    		}else {
    			if(data[i]>sec_Number) {
    				sec_Number = data[i];
    			}
    		}
    	}
    	return sec_Number;
    }
    

    结果展示
    在这里插入图片描述

    展开全文
  • 题目来自leetcode的215道题,寻找数组中K个最大,如果要寻找一个数组的最大,可能很简单,但是寻找K个最大,可能就不是那么简单了,当然这道题目有多个解法 一种解法,排序法,想要找到K元素,...

    题目来自leetcode的215道题,寻找数组中的第K个最大值,如果要寻找一个数组的最大值,可能很简单,但是寻找第K个最大值,可能就不是那么简单了,当然这道题目有多个解法

    第一种解法,排序法,想要找到第K大的元素,比较好的方法可能是排序法,经过排序的数组可以直接通过索引找到第K个值,这个值自然就是数组中第K大的值

    在这里插入图片描述
    在这个数组中,如果要寻找第2大的值,那么结果就是5
    在这道题中,可以采用各种排序法,例如归并排序和快速排序等,很明显算法的时间复杂度是O(nlogn)
    那么通过排序就能完成这道题目了

    第二种解法,通过快速排序的思想,快速的完成这道题目,让时间复杂度降到O(n)级别的吧,性能更加的优秀。
    快速排序的思想便是在第一遍排序过后,中间的值就是当前数组的中间值,左边都是小于它的值,右边则都是大于它的值
    那么如果第一次排序后中间值的索引刚好等于k,那么代表已经找到这个值,直接返回中间值的数值即可。
    但是如果中间值的索引大于k,那么代表k值在左边的区域,反之如果中间值的索引小于k,那么代表k值在右边的区域。需要注意这里的k索引并不是题目传进来的那一个k值,在算法开始的时候需要进行转换
    有了这个信息后,就只需要寻找一边的元素就可以了,因为已经能确定k在哪一边。

    代码如下

    public int findKthLargest(int[] nums, int k) {
            //请注意这里的k是需要转换的,因为是取第k大的数,所以传过来的k并不是要查的k
            k = nums.length - k;
            int result = quickSort(nums, 0, nums.length - 1,k);
            return result;
        }
        private  int quickSort(int[] nums, int l, int r,int k) {
            //找到关键点p,此时索引p对应的值即是数组中的中间值
            int p = partition(nums,l,r);
            //递归终止条件,如果索引p等于k,那么代表索引p的值就是结果k值,那么直接返回索引p的值即可
            if(p==k) {
                return nums[p];
            }
            //如果p大于k,那么代表第k大的值在p的左边,此时左边的数组是未排序的,但能确定的是左边的值都比p的值要小
            int result = 0;
            if(p>k){
                result = quickSort(nums,l,p-1,k);
            }else {
                //如果p小于等于k,那么代表第k大的值在p的右边,此时右边的数组是未排序的,但能确定的是右边的值都比p的值要大
                result = quickSort(nums,p+1,r,k);
            }
            return result;
        }
    
        //返回值是下标p,p左边的元素都小于p的元素,p右边的元素都大于p的元素。试着用一次遍历,使用原地排序,不创建新的空间,来完成吧!
        public  int partition(int[] arr, int l, int r){
            // 生成 [l, r] 之间的随机索引
            int p = l + (new Random()).nextInt(r - l + 1);
            swap(arr, l, p);
    
            //记录开始的值
            int j = l;
            for (int i = l+1; i <= r; i++) {
                //System.out.println(arr[i]);
                if(arr[i]<=arr[l]){
                    j++;
                    //交换索引j和索引i的值
                    swap(arr,i,j);
                }
            }
            //最后再将left元素与下标j元素交换就可以了
            swap(arr,l,j);
            return j;
        }
    
        public  void swap(int[] arr,int i,int j){
            int temp;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
    public static void main(String[] args) {
            int[] arr = {3,2,1,5,6,4};
            int k = 1;
            System.out.println(findKthLargest(arr,k));
    
            int[] arr2 = {3,2,3,1,2,4,5,5,6};
            int k2 = 4;
            System.out.println(findKthLargest(arr2,k2));
        }
    

    在这里插入图片描述

    时间复杂度O(n)是怎么得到的?
    进行第一次快排后,需要扫描整个数组一次,就是对n个元素进行操作,到后面只需要操作一边就可以了,但是因为快速排序是随机算法,两边的元素可能不均等,因此通过期望可以大概得出每一边的元素为n/2
    因此在最坏的情况下
    需要的时间大约为n+n/2+n/4+…+1 ≈ 2n,因此是O(n)级别的算法。

    当然partition也可以选择双路快速排序

    private int partition(int[] arr, int l, int r){
    
            // 生成 [l, r] 之间的随机索引
            int p = l + (new Random()).nextInt(r - l + 1);
            swap(arr, l, p);
    
            // arr[l+1...i-1] <= v; arr[j+1...r] >= v
            int i = l + 1, j = r;
            while(true){
    
                while(i <= j && arr[i] < arr[l])
                    i ++;
    
                while(j >= i && arr[j] > arr[l])
                    j --;
    
                if(i >= j) break;
    
                swap(arr, i, j);
    
                i ++;
                j --;
            }
    
            swap(arr, l, j);
            return j;
        }
    
    展开全文
  • java 寻找数组中第k

    千次阅读 2016-12-03 17:25:21
    1.排序 public static int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; }2.通过堆 public static int findKthLargest(int[] nums, i

    转载请注明来自:黄朝辉的博客

    0.前言

    在未排序的数组中查找第k大的数。这里不对k的值进行判断了,认为它是合法的。

    1.排序

        public static int findKthLargest(int[] nums, int k) {
            Arrays.sort(nums);
            return nums[nums.length - k];
        }

    时间复杂度为O(nlog(n))。

    2.通过堆

        public static int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> q = new PriorityQueue<Integer>(k);
            for (int i : nums) {
                q.offer(i);
    
                if (q.size() > k) {
                    q.poll();
                }
            }
    
            return q.peek();
        }

    时间复杂度为O(nlog(k)),空间复杂度为 O(k) 。

    3.快排

        public static int findKthLargest(int[] nums, int k) {
            if (k < 1 || nums == null) {
                return 0;
            }
    
            return getKth(nums.length - k + 1, nums, 0, nums.length - 1);
        }
    
        public static int getKth(int k, int[] nums, int start, int end) {
    
            int pivot = nums[end];
    
            int left = start;
            int right = end;
    
            while (true) {
    
                while (nums[left] < pivot && left < right) {
                    left++;
                }
    
                while (nums[right] >= pivot && right > left) {
                    right--;
                }
    
                if (left == right) {
                    break;
                }
    
                swap(nums, left, right);
            }
    
            swap(nums, left, end);
    
            if (k == left + 1) {
                return pivot;
            } else if (k < left + 1) {
                return getKth(k, nums, start, left - 1);
            } else {
                return getKth(k, nums, left + 1, end);
            }
        }
    
        public static void swap(int[] nums, int n1, int n2) {
            int tmp = nums[n1];
            nums[n1] = nums[n2];
            nums[n2] = tmp;
        }

    平均时间复杂度为O(n),最坏情况下为O(n^2)。

    展开全文
  • 寻找数组中第二小的元素

    千次阅读 2019-02-23 20:53:20
    寻找数组中第二小的元素 示例代码一:先把数组进行升序排序 排完序后再进行遍历比较 public static void main(String[] args) { int arr[]={-4,-4,56,34,76,34,23,4,75,87,50,3,5,6,}; //冒泡排序 for(int i...
  • 问题:寻找数组中K元素。最简单的想法是直接进行排序,算法复杂度是O(N*logN)。这么做很明显比较低效率,因为不要求别的信息只要计算出K元素。当然,如果在某种情况下需要频繁访问K元素就可以先...
  • 问题1:寻找数组中K元素。public class FindMaxKNum { public static void main(String args[]) { int a[] = new int[]{3,5,2,8,-1,7,1,10}; System.out.println(findKMaxNum(a, 0, a.length - 1, 6));
  • 求数组的最大与最小值package demos.array; /** ... * 寻找数组中的最大与最小值 */ public class MaxAndMin { static int Max; static int Min; public static void getMaxAndMin(int[] ...
  • 给出一个分治算法来找出n个元素序列中第二大元素。 我选择的分治算法是快速排序算法。 数组通过随机数来产生。 代码实现如下: package 实验测试; import java.util.Scanner; public class SIX { public ...
  • 寻找数组中第n元素

    千次阅读 2018-04-20 15:46:59
    0x00 问题简述给定一个数组,找出该数组中第n元素。其中,1&lt;=n&lt;=length。例如,给定一个数组A={2,3,6,5,7,9,8,1,4},当n=1时,返回9。0x01 先排序我拿到这个问题的地思路就是先排序...
  • Java找出数组中第二大

    千次阅读 2019-10-09 20:13:49
    题目: 给出一个数组{7,3,19,40,4,7,1};...另一个变量用来存储数组元素第二大数,初始为最小负整数,然后遍历数组元素。 实现: public static int findSecMax(int[] arr) { int max = arr[0]; //...
  • 如果k=6,也就是要寻找第6元素,很显然,数组中第一大元素是24,第二大元素是20,第三大元素是17...... 第六大元素是9。 方法一:排序法 这是最容易想到的方法,先把无序数组到小进行排序,排序后的第k个...
  • 寻找数组中最大

    2019-12-10 19:12:43
    第二行为数组的各个元素。 输出格式  输出最大,及其下标 样例输入 3 3 2 1 样例输出 3 0 根据题意,我们先输入n,接着输入n个数字 在输入的数字只有一个时,第一个数字就是最大的数字max 后面还有输...
  • * 利用快排寻找数组中第k个最大元素 */ public class FindFirstKElement { //快排 public static int getBaseIndex(int[] arr, int start, int end) { int base = arr[start]; while(start &lt; end) { ...
  • 经典算法题:寻找数组中第k元素

    万次阅读 多人点赞 2018-06-13 18:54:06
    比如,对于数组a={1,2,2,2,3,3,3},第二大元素应该是3还是2呢?本文作这种分类:如果第二大元素是3,说明在处理第k元素时不处理重复的数据,也就是将原数组进行降序排序后,下标为k-1的元素。这种处理方法称...
  • 方法一:排序法,先把这个无序数组进行排序,假设按照从小到排,则k个元素就是数组中k大元素。 排序的时间复杂度最快为o(nlogn) 下面用快速排序实现: #include&lt;iostream&gt; template&lt;...
  • 题目描述:对于一个具有 n 个元素数组,用一个天平,通过比较 2元素的重量,求出第二重的一个。 代码如下: import numpy as np def SecondMax(a): Max = a[0] # 假设第一个元素为最大 secondMax = -1 ...
  • 给定一个非空数组,返回此数组中第的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。 示例 1: 输入: [3, 2, 1] 输出: 1 解释: 的数是 1. 示例 2: 输入: [1, 2] 输出: 2 ...
  • 算法训练 寻找数组中最大 时间限制:1.0s 内存限制:512.0MB   问题描述  对于给定整数数组a[],寻找其中最大,并返回下标。 输入格式  整数数组a[],数组元素个数小于1等于100。输出...
  • Java实现 蓝桥杯 算法训练 寻找数组中最大

    万次阅读 多人点赞 2019-06-11 19:11:41
    算法训练 寻找数组中最大 时间限制:1.0s 内存限制:512.0MB 提交此题 问题描述  对于给定整数数组a[],寻找其中最大,并返回下标。 输入格式  整数数组a[],数组元素个数小于1等于100。输出数据分作两行:一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 142,226
精华内容 56,890
关键字:

寻找数组元素中的第二大值