8.25 数组中未出现的最小正整数

题目】:

  给定一个无序整型数组arr,找到数组中未出现的最小正整数

  举例:

    arr=[-1, 2, 3, 4],返回1

    arr=[1, 2, 3, 4],返回5

题目来源:左程云老师《程序员代码面试指南》

原文地址:https://www.cnblogs.com/latup/p/10205040.html

时间: 01-01

8.25 数组中未出现的最小正整数的相关文章

[算法]数组中未出现的最小正整数

题目: 给定一个无序整型数组arr,找到数组中未出现的最小正整数. 例如: arr=[-1,2,3,4].返回1. arr=[1,2,3,4].返回5. 要求时间复杂度为O(N),空间复杂度为O(1). 解答: 在遍历arr之前先生成两个变量.变量l表示遍历到目前为止,数组arr已经包含的正整数范围是[1,l],所以在没有开始之前l=0,表示arr没有包含任何正整数.变量r表示遍历到目前为止,在后续出现最优状况的情况下,arr可能包含的正整数范围是[1,r],所以在没有开始之前,令r=N,r同时

数组中未出现的最小正整数

给定一个未排序的整数数组,让我们求得未出现的最小正整数(要求时间o(n)空间复杂度o(1)) 如果一般的方法,应该是先排序,然后遍历的时候直接找到正整数,但是排序最小也要o(n*log(n))的复杂度.这里运用了夹逼的办法(代码如下) 1 void swap(int &a,int &b) 2 { 3 int temp = a; 4 a = b; 5 b =temp; 6 7 8 } 9 int Number(int *arr,int size) 10 { 11 int r = size;

找出数组中从未出现的最小正整数java实现

1 /** 2 * 找出未出现的最小正整数 3 * @param A 4 * @param n 5 * @date 2016-10-7 6 * @author shaobn 7 */ 8 public static int findArrayMex(int[] a,int n){ 9 int count = n; 10 int temp = 0; 11 int dir = 1; 12 int num = 0; 13 for(int i = 0;i<count-1;i++){ 14 if(a[i]

N个数中未出现的最小整数

Description 给出一串数字,这串数字由 n 个数 ai 组成,找出未出现在这串数字中的最小正整数 Input 输入第一行为一个正整数 n (1 <= n <= 1000) 第二行为 n 个正整数 ai ( 1 <= ai <= 1000000000) Output 输出没有出现在这 n 个正整数中的最小的正整数 Sample Input 5 2 4 3 5 151 100 101 102 103 Sample Output 62 思路 因为n的大小为1000,所以没有出现

[算法]在数组中找到一个局部最小的位置

题目: 定义局部最小的概念.arr长度为1时,arr[0]是局部最小.arr的长度为N(N>1)时,如果arr[0]<arr[1],那么arr[0]为局部最小.如果arr[N-1]<arr[N-2],那么arr[N-1]是局部最小.如果0<i<N-1,arr[i]<arr[i+1]&&arr[i]<arr[i-1],那么arr[i]是局部最小. 给定无序数组arr,已知arr中任何两个相邻的数不相等.写一个函数,只需返回arr中任何一个局部最小出现

[经典面试题]排序数组中绝对值最小元素

[题目] 题目为: 有一个已经排序的数组(升序),数组中可能有正数.负数或0,求数组中元素的绝对值最小的数,要求,不能用顺序比较的方法(复杂度需要小于O(n)),可以使用任何语言实现 例如,数组{-20,-13,-4, 6, 77,200} ,绝对值最小的是-4. [分析] 给定数组是已经排好序的,且是升序,没有重复元素. 一个简单的思路,就是一次性遍历数组,求出数组的元素的绝对值的最小值,这样的时间复杂度为O(n). 但是,这样就浪费了题目的一个条件:数组是已经排好序的.所以,需要对原来的题目

无序数组同时查找最大和最小的元素

在无序数组中查找最大或者最小的元素都需要进行n次比较,但是同时查找最大和最小的元素却可以在3n/2次比较内实现. 问题:给定一个长度为n的无序序列,同时查找出这个序列中的最大和最小值. 算法设计:如果只是在无序序列中查找最大或最小值,至少需要n-1次比较,但是同时查找出最大值和最小值却不需要2(n-1)次比较,而只需要3n/2次比较.其策略是:同时保存当前得到的最大值和最小值,之后依次从无序序列中取出两个数并进行比较,其中较小的一个与当前的最小值比较,较大的一个于当前的最大值比较,然后更新当前的

未排序数组中累加和为指定值得最长子数组序列问题

1.题目: 给定一个无序数组,其中元素 可正可负可0,给定一个k,求arr中所有的子数组累加和为k的最长子数组长度. 1 // maxLength.cpp : 定义控制台应用程序的入口点. 2 //未排序数组中累加和为指定值的最长子数组长度 3 //数组元素可正.可负.可0 4 5 #include "stdafx.h" 6 #include<iostream> 7 #include <map> 8 #include <iterator> 9 10

找到无序数组中最小的k个数

题目:给定一个无序整数数组arr,找到其中最小的k个数 要求:如果数组arr的长度为n,排序之后自然可以得到最小的k个数,此时时间复杂度与排序的时间复杂度相同均为O(NlogN),本题要求实现时间复杂度为O(NLogK). 1.O(NLogK)的方法,即一直维护一个有k个数的最大的大根堆,这个堆是目前选出的k个最小数,在堆里的k个元素中堆顶的元素是最大的一个. 接下来遍历整个数组,遍历的过程中看当前数是否比堆顶元素小.如果是,就把堆顶的元素替换成当前的数,然后从堆顶的位置调整堆,替换后堆的最大元

转:最小区间:k个有序的数组,找到最小区间使k个数组中每个数组至少有一个数在区间中

转:http://www.itmian4.com/thread-6504-1-1.html 最小区间原题 k个有序的数组,找到最小的区间范围使得这k个数组中,每个数组至少有一个数字在这个区间范围内.比如: 数组1:[4, 10, 15, 24, 26] 数组2:[0, 9, 12, 20] 数组3:[5, 18, 22, 30] 最小的区间是[20, 24],这个区间包含了数组1中的24,数组2中的20,数组3中的22 思考时间~~~ 分析 该题看起来还算比较简单,大家通常都会想到:为每一个数组