精华内容
下载资源
问答
  • 寻找数组元素中的第二大值
    千次阅读
    2018-07-17 11:33:11

     

    如何找出数组中的第二大数

    算法思路:

    方法1:

      快速排序后根据数组下标获得数组中第二大的值

    方法2:

    (1)首先定义一个变量来存储数组的最大数,初始值为数组首元素;另一个变量用来存储数组元素的第二大数,初始值为最小负数 -32767,然后遍历数组元素。

    (2)如果数组元素的值比最大数变量的值大,则将第二大变量的值更新为最大数变量的值,最大数变量的值更新为该元素的值;如果数组元素的值比最大数的值小,则判断该数组元素的值是否比第二大数的值大,如果大,则更新第二大数的值为该数组元素的值。

    代码实现:

    package Array;
    
    /**
     * 获取数组中第二大的数
     */
    public class SecondMax {
        public static int FindSecMax(int data[]){
            int count = data.length;
            int maxnumber = data[0];
            int sec_max = Integer.MIN_VALUE;//最小负整数
            for (int i=1;i<count;i++){//循环遍历一遍
                if (data[i]>maxnumber){//当前数组元素的值是比最大的数大
                    sec_max=maxnumber;//更新第二大的数值为先前的最大值
                    maxnumber = data[i];//更新先前的最大值为当前数组元素的值
                }
                else{
                    if (data[i]>sec_max){//当前数组元素的值是比最大值小则与第二大值比较
                        sec_max = data[i];//如果当前数组元素的值比第二大值大,则更新第二大值
                    }
                }
            }
            return sec_max;
        }
        public static void main(String[] args){
            int[] array = {7,3,19,40,4,7,1};
            System.out.println(FindSecMax(array));
        }
    }
    

     

     

     

     

     

    更多相关内容
  • 主要介绍了Go语言算法之寻找数组第二大元素的方法,以实例形式分析了不排序、只循环一次来实现寻找数组第二大元素的技巧,是比较典型的算法,需要的朋友可以参考下
  • 寻找数组中K个最大元素

    千次阅读 2020-11-11 19:37:42
    题目来自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;
        }
    
    展开全文
  • 数组第二大元素

    2022-08-12 22:58:48
    数组第二大元素

    题目描述:

    给定数组arr,最多只能遍历该数组一次,求出数组的第二大元素。

    用两个变量即可实现。这两个变量分别保存数组的最大元素和第二大元素,分别记作max1和max2,最终返回max2。

    网上找了几个帖子,发现写的代码都有问题,没有考虑到数组最开始两个或多个元素重复的情况。除非数组所有元素都是同一个值,否则需要确保在遍历数组时,max1必须大于max2。

    如果数组最开始的几个元素都相等,则需要先找到第一个两相邻元素不相等的数组下标,然后从这个下标开始再往后遍历,根据具体的元素值选择性地更新max1和(或)max2。

    还要注意,如果数组某个元素的值大于max1,则需要在更新max1之前,必须先把max1现有的值赋予max2,再将max1自己更新。如果元素值介于max1和max2之间,只更新max2即可。

    以下贴出正确代码实现:

    import java.util.Arrays;
    import java.util.HashSet;
    import java.util.Set;
    
    /**
     * 求数组第二大元素
     */
    public class GetSecondaryMaxValue {
    
        public static void main(String[] args) {
            int[] arr1 = {3, 4, 2, 5, 7, 6};       // 6
            int[] arr2 = {2, 9, 10, 9, 4, 1, 5};   // 9
            int[] arr3 = {5, 5, 5, 3, 3};          // 3
            int[] arr4 = {3, 3, 2, 3};             // 2
            int[] arr5 = {8, 8, 9, 9, 9};          // 8
            int[] arr6 = {5, 6, 6};                // 5
            int[] arr7 = {0, 1, 2, 3, 4, 5};       // 4
            int[] arr8 = {8, 7, 6, 5, 4, 3, 2, 1}; // 7
            // 以上测试用例全部通过
            System.out.println(getSecondMaxElement(arr1));
            System.out.println(getSecondMaxElement(arr2));
            System.out.println(getSecondMaxElement(arr3));
            System.out.println(getSecondMaxElement(arr4));
            System.out.println(getSecondMaxElement(arr5));
            System.out.println(getSecondMaxElement(arr6));
            System.out.println(getSecondMaxElement(arr7));
            System.out.println(getSecondMaxElement(arr8));
            // 用对数器验证
            boolean success = true;
            for (int i = 0; i < 1000000; i++) {
                int length = 3 + (int)(10 * Math.random());
                int[] arr = generateRandomArray(length);
                int result = getSecondMaxElement(arr);
                int result0 = getSecondMaxElement0(arr);
                if (result0 != result) {
                    success = false;
                    break;
                }
            }
            System.out.println(success ? "OK" : "Failed!");  // OK
        }
    
        /**
         * 主方法
         */
        private static int getSecondMaxElement(int[] arr) {
            if (arr == null || arr.length < 2) {
                throw new IllegalArgumentException();
            }
            // max1:最大元素
            // max2:第二大元素
            int max1 = Math.max(arr[0], arr[1]), max2 = Math.min(arr[0], arr[1]);
            int from = 2;
            while (max2 == max1 && from < arr.length) {
                // 找出第一个max1与max2不相等的位置from
                max1 = Math.max(arr[from - 1], arr[from]);
                max2 = Math.min(arr[from - 1], arr[from]);
                from++;
            }
            for (int i = from - 1; i < arr.length; i++) {
                if (arr[i] > max2 && arr[i] < max1) {
                    max2 = arr[i];
                } else if (arr[i] > max1) {
                    max2 = max1;
                    max1 = arr[i];
                }
            }
            return max2;
        }
    
        /**
         * 对照方法
         */
        private static int getSecondMaxElement0(int[] arr) {
            Set<Integer> set = new HashSet<>(arr.length);
            for (int a : arr) {
                set.add(a);
            }
            int[] dest = new int[set.size()];
            int k = 0;
            for (int a : set) {
                dest[k++] = a;
            }
            Arrays.sort(dest);
            return (dest.length < 2) ? dest[0] : dest[dest.length - 2];
    
        }
    
        /**
         * 生成随机数组
         */
        private static int[] generateRandomArray(int length) {
            if (length < 0) {
                throw new IllegalArgumentException();
            }
            int[] arr = new int[length];
            for (int i = 0; i < length; i++) {
                arr[i] = (int) (100 * Math.random());
            }
            return arr;
        }
    
    }
    

    展开全文
  • 问题描述  对于给定整数数组a[],寻找其中最大,并返回下标。 输入格式  整数数组a[],数组元素个数小于1等于100。...第二行为数组的各个元素。 输出格式  输出最大,及其下标 样例输入 3 3 2 1 样例输出 3 0
  • 寻找数组中第二小的元素

    千次阅读 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...

    寻找数组中第二小的元素

    示例代码一:先把数组进行升序排序 排完序后再进行遍历比较

     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=0;i<(arr.length)-1;i++){
                for(int j=0;j<arr.length-i-1;j++){
                    if(arr[j]>arr[j+1]){
                        int temp=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=temp;
                    }
                }
            }
            int secondNum=arr[0];
            for (int i=0;i<arr.length;i++){
                if(arr[i]>secondNum){
                    secondNum=arr[i];
                    break;
                }
            }
            System.out.println("secondNum---->"+secondNum);
        }

    方法二:

    public static void main(String[] args) {
    
            int arr[]={-87,-97,23,90,12,-87,-87};
    
            int firstmin = Integer.MAX_VALUE;   //第一小的元素  初始值设为int的最大取值
            int secondmin = Integer.MAX_VALUE;   //第二小的元素  初始值设为int的最大取值
    
            for(int value:arr){
                if (value < firstmin) //小于最小的元素 更新1和2
                {
                    secondmin = firstmin;
                    firstmin = value;
                }
                else if (value < secondmin && value != firstmin) //小于倒数二的 更新2
                {
                    secondmin = value;
                }
            }
            System.out.println("firstmin--------->"+firstmin);
            System.out.println("secondmin--------->"+secondmin);
    }

    方法三:

    
     public static void main(String[] args) {
    
            int arr[]={34,12,23,90,12,-87,-27};
            Arrays.sort(arr);  //排序  升序
            int secondNum=arr[0];
            for(int i=1;i<arr.length;i++){
                if(arr[0]<arr[i]){
                    secondNum=arr[i];
                    break;
                }
            }
            System.out.println(secondNum);
    }

     

    展开全文
  • 寻找数组中第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 先排序我拿到这个问题的地思路就是先排序...
  • 寻找数组中第二大的数字 解题思路: 先定义两个变量:一个变量用来存储数组的最大数,初始为数组第一个数,另外一个变量存储数组元素第二大数字,初始为最小负整数,遍历数组并进行判断。 代码展示 public ...
  • 【C++】寻找数组第k大元素

    千次阅读 2022-03-24 21:23:27
    题目:给定整数数组nums和整数k,请返回数组中第k个最大的元素。 注意:你需要找的是数组排序后的k个最大的元素,而不是k个不同的元素。 要求:时间复杂度为 O(N) 看到这个问题,我们脑袋里一个想到的就是...
  • 比如给定的无序数组如下所示:如果k=6,也就是要寻找第6元素,很显然,数组中第一大元素是24,第二大元素是20,第三大元素是17...... 第六大元素是9。方法一:排序法这是最容易想到的方法,先把无序数组到小...
  • Java程序查找数组中第二大数字

    千次阅读 2021-03-18 09:24:48
    要查找给定数组的第二大元素,首先,对数组进行排序。排序数组比较数组的前两个元素如果第一个元素大于第二元素,则将其交换。然后,如果第二元素大于第三个元素,则比较第二个和第三个元素。重复此操作,直到...
  • 数组中第2大元素

    千次阅读 2017-07-14 21:56:06
    if(data[i]>secMax){//如果该元素比最大的小,再与当前第二大的比较,如果比当前第二大,则赋值给secMax secMax = data[i]; } } } return secMax; }//findSecMax } //输出58,亲测正确 T(n)= O(n) ...
  • 数组元素比最大还小并且比第二大的数要,更新第二大的数;其中:INT_MAX和INT_MIN是C/C++的常量,分别表示最大最小整数,头文件是limits.h。思想:只通过一遍扫描数组找到第二大数;...
  • 寻找数组中的峰值(极大值)

    千次阅读 2021-01-10 20:10:36
    峰值元素是指其大于左右相邻元素。 给定一个输入数组nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。 数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。 你可以假设nums...
  • 寻找数组第k大元素和上篇选择排序算法相似,只是分割之后舍弃另一半数据。 #include <cassert> #include <iostream> using namespace std; // // 交换 数组两个元素 // void swap(int *data, int a,...
  • 题目:在未排序的数组中找到 k 个最大的元素。请注意,你需要找的是数组排序后的 k 个最大的元素,而不是 k 个不同的元素 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4...
  • 寻找数组中第K的数

    千次阅读 2020-12-11 11:30:28
    给定一个数组A,要求找到数组A中第K的数字。对于这个问题,解决方案有不少,此处我只给出三种:方法1:对数组A进行排序,然后遍历一遍就可以找到K的数字。该方法的时间复杂度为O(N*logN)方法2:利用简单选择...
  • 方法一将数组到小排序然后找第二个 <!doctype html> <html lang="en"> <head> <meta charset="UTF-8"> <title>网页</title> <script> var arr=[5,2,10,8,0,4,7,11,...
  • 经典算法题:寻找数组中第k元素

    万次阅读 多人点赞 2018-06-13 18:54:06
    比如,对于数组a={1,2,2,2,3,3,3},第二大元素应该是3还是2呢?本文作这种分类:如果第二大元素是3,说明在处理第k元素时不处理重复的数据,也就是将原数组进行降序排序后,下标为k-1的元素。这种处理方法称...
  • C语言:查找数组中最大的元素值

    千次阅读 2021-12-05 22:57:51
    1.查找数组中最大的元素值。 #include <stdio.h> int main() { int array[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}; int loop, largest; largest = array[0]; for(loop = 1; loop < 10; loop++) { if...
  • #include #define N 5 void f(int a[],int n,int *l,int *s_l); int main() { int a[N],l,s_l,i; for(i=0;i;i++) scanf("%d",&*(a+i));... for(i=2;...注意如果有元素大于*l的话,将*l的原值顺延给*s_l .
  • 数组中第k个最大元素 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的 k 个最大的元素,而不是 k 个不同的元素。 示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 ...
  • 寻找无序数组中K大元素

    千次阅读 2019-01-23 17:31:33
    方法一:排序法,先把这个无序数组进行排序,假设按照从小到排,则k个元素就是数组中k大元素。 排序的时间复杂度最快为o(nlogn) 下面用快速排序实现: #include&lt;iostream&gt; template&lt;...
  • C语言 · 寻找数组中的最大

    千次阅读 2021-05-18 14:58:29
    问题描述对于给定整数数...第二行为数组的各个元素。输出格式输出最大,及其下标样例输入33 2 1样例输出3 0思路:对于给定整数数组a[],寻找其中最大,并返回下标。#includeint maxfun(int a,int b);int main(){i...
  • 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的 k 个最大的元素,而不是 k 个不同的元素。 示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2: 输入: [3,2...
  • 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的 k 个最大的元素,而不是 k 个不同的元素。 ... 这里说三个方法,再讲讲三种方法的优劣 一种:排序 ...
  • 寻找无序数组k大元素

    千次阅读 2019-01-04 16:34:06
    问题:给定一个无序数组,找出该无序数组k大元素。 思路:1.先排序,那么k个元素自然就是k元素了。 2.使用最小堆,先利用前k个元素建立最小堆,再往后比较,如果有比堆顶元素大的,则调整最小堆,最后...
  • 从一个给定的、无序的数组中,找出第二大或者第二小的数值。#include int FindSecondBiggest(int *v, int len){if (v == NULL || len < 2) {return 0xfffffff;}int i, max = v[0], second = v[1];if (max < ...
  • Java实现 蓝桥杯 算法训练 寻找数组中最大

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 163,036
精华内容 65,214
热门标签
关键字:

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