-
旋转数组的最小数字(十)
2020-05-16 11:21:20题目 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。...为了便于分析,我们先将数组中的数画在二维坐标系中,横坐标表示数组下标,纵坐标表示数值,如下所示: 图中水平的实线段表示相同元素。题目
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个升序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
数组可能包含重复项。
注意:数组内所含元素非负,若数组大小为0,请返回-1。
样例
输入:nums=[2,2,2,0,1]输出:0
算法:
(二分) O(n)
为了便于分析,我们先将数组中的数画在二维坐标系中,横坐标表示数组下标,纵坐标表示数值,如下所示:
图中水平的实线段表示相同元素。
我们发现除了最后水平的一段(黑色水平那段)之外,其余部分满足二分性质:竖直虚线左边的数满足 nums[i]≥nums[0];而竖直虚线右边的数不满足这个条件。
分界点就是整个数组的最小值。所以我们先将最后水平的一段删除即可。
另外,不要忘记处理数组完全单调的特殊情况:
当我们删除最后水平的一段之后,如果剩下的最后一个数大于等于第一个数,则说明数组完全单调。
时间复杂度分析
二分的时间复杂度是 O(logn),删除最后水平一段的时间复杂度最坏是 O(n),所以总时间复杂度是 O(n)。class Solution { public int findMin(int[] nums) { int n = nums.length - 1; if(n < 0) return -1; #去除右端水平黑线 while(n > 0 && nums[n] == nums[0]) n--; #如果右端为空的话那么就只剩竖直虚线左半部分,最小的就是最左端 if(nums[n] >= nums[0]) return nums[0]; int l = 0,r = n; while(l < r){ int mid = l + r >> 1; if(nums[mid] < nums[0]) r = mid; else l = mid + 1; } return nums[r]; } }
-
在数组x的十个数中求平均值v,找出与v相差最小的数组元素
2019-11-04 11:42:54在数组x的十个数中求平均值v,找出与v相差最小的数组元素(题目来源:c语言程序设计第三版) #include<stdio.h> #include<math.h> int main() { double a[10],aver,sum,det[10],min; int i; for(i=0;...在数组x的十个数中求平均值v,找出与v相差最小的数组元素(题目来源:c语言程序设计第三版)
#include<stdio.h> #include<math.h> int main() { double a[10],aver,sum,det[10],min; int i; for(i=0;i<10;i++) { printf("请输入一个数:\n"); scanf("%lf",&a[i]); sum+=a[i]; } aver=sum/10; for(i=0;i<10;i++) { det[i]=aver-a[i]; det[i]=fabs(det[i]); } min=a[0]; for(i=1;i<10;i++) { if(det[i]<=det[i-1]) min=a[i]; } printf("该数组的平均值v=%lf\n",aver); printf("与平均数差值最小的数组元素为%lf",min); return 0; }
对于两个或者多个数与平均值的差相等的情况下,还不能完备地全部输出值,需要改进。
-
剑指offer系列(十三)把数组排成最小的数,丑数,把数组排成最小的数
2018-09-13 17:17:15输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 解题思路: 把数字转换为字符串,然后...把数组排成最小的数
题目描述
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。
解题思路:
把数字转换为字符串,然后cmp比较大小,升序排列后输出。
cmp(x,y) 函数用于比较2个对象,如果 x < y 返回 -1, 如果 x == y 返回 0, 如果 x > y 返回 1
代码:
map 与lambda关系参考:https://www.jianshu.com/p/07737690901e
# -*- coding:utf-8 -*- #把数组排成最小的数 class Solution: def PrintMinNumber(self, numbers): # write code here import operator if not numbers: return '' numbers = list(map(str, numbers))#转为字符串 numbers.sort(cmp=lambda x,y: int(x+y)-int(y+x))#数字比较 if numbers[0] == '0': return 0 else: return ''.join(numbers)
丑数
题目描述
把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
解题思路:
按顺序把每个丑数放在数组中,求下一个丑数。下一个丑数必定由有数组中的某一个丑数A * 2, B * 3, C * 5 的中的最小值得来。
分析:在数组中必定有一个丑数M2, 在它之前的数 * 2 都小于当前最大丑数, 在它之后的数 * 2都大于当前最大丑数,
同样有M3, M5代码:
# -*- coding:utf-8 -*- class Solution: def GetUglyNumber_Solution(self, index): # write code here if index<1: return 0 res = [1] t2 = t3 = t5 = 0 nextdex = 1 while nextdex < index: minNum = min(res[t2]*2, res[t3]*3, res[t5]*5) res.append(minNum) #step步伐很小,每一个数都考虑到 while res[t2]*2 <= minNum: t2 +=1 while res[t3]*3<= minNum: t3 +=1 while res[t5]*5 <= minNum: t5 +=1 nextdex +=1 return res[nextdex-1]
第一个只出现一次的字符
题目描述
在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).
解题思路:
先对每个字符出现的字符进行个数统计,然后再对原字符串进行遍历,找出第一个出现次数为1的字符
代码:
# -*- coding:utf-8 -*- class Solution: def FirstNotRepeatingChar(self, s): # write code here from collections import Counter count = Counter(s) if not s: return -1 for i,c in enumerate(s): if count[c] == 1: return i
-
找出数组中最大(小)的十个数
2019-07-15 16:47:57找出数组中最大(小)的十个数最小(大)堆实现思路快速排序实现思路注意 最小(大)堆实现 思路 要找出数组中最大的10个数,建立一个容量为10的最小堆,遍历数组,当最小堆容量小于10的时候直接push,当容量大于10...最小(大)堆实现
思路
要找出数组中最大的10个数,建立一个容量为10的最小堆,遍历数组,当最小堆容量小于10的时候直接push,当容量大于10的时候,数组的数和最小堆的堆顶的数进行比较,如果小于堆顶数则不可能是最大的10个数之一,如果大于则和堆顶数进行交换,一直遍历完数组
import java.util.Random; class Test { private static int ptr = 1; private static int[] heap= new int[6]; private static int[] num = new int[30]; public static void main(String[] args) { Random rand = new Random(); for(int i = 0; i < 30; i++) { num[i] = rand.nextInt(100); System.out.println(num[i]); } for(int i = 0; i < 30; i++) { push(num[i]); } System.out.println(); for(int i = 1; i < 6; i++) { System.out.println(heap[i]); } } public static void push(int x) { if(ptr <= 5) { heap[ptr++] = x; adjustUp(ptr-1); } else { if(x <= heap[1]) { return; } heap[1] = x; adjustDown(); } } public static void adjustDown() { for(int i = 1; i * 2 <= 5; ) { int next = 2*i; if(next+1 <= 5 && heap[next] > heap[next+1]) { next++; } if(heap[i] > heap[next]) { swap(heap, i, next); i = next; } else { return; } } } public static void adjustUp(int current) { for(int i = current; i > 1; i /= 2) { if(heap[i] < heap[i/2]) { swap(heap, i, i/2); } else { return; } } } public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j] ; arr[j] = temp; } }
快速排序实现
思路
快速排序的时候是先找到一个中间数,这个中间数的左边的数都比这个数小,中间数的右边的数都比这个数大,当要找出最小的10个数的时候,只要找出中间数等于10,它左边的所有数就是最小的十个数
注意
- 一定可以得到中间数是我们想要的数量,因为快速排序是一直递归进行直到得到两个数的快排或者一个数的快排
- 得到中间数有两种情况,一种是 low == high 即将返回的时候,另一种是继续递归的时候,这两种情况都有可能,都要考虑,不然只在某些情况输出结果,某些情况没有输出
import java.util.Random; class Test{ private static int[] arr = new int[30]; public static void main(String[] args) { Random rand = new Random(); for(int i = 0; i < 30; i++) { arr[i] = rand.nextInt(100); } quickSort(arr, 0, 29); } public static void quickSort(int[] num, int low, int high) { if(low >= high) { //第一种情况 if(low == 5) { for(int i = 0; i < 5; i++) { System.out.println(arr[i]); } } return; } int middle = getMiddle(num, low, high); //第二种情况 if(middle == 5) { for(int i = 0; i < 5; i++) { System.out.println(arr[i]); } } quickSort(num, low, middle-1); quickSort(num, middle+1, high); } public static int getMiddle(int[] num, int low, int high) { int temp = num[low]; while(low < high) { while(low < high && num[high] >= temp) high--; num[low] = num[high]; while(low < high && num[low] <= temp) low++; num[high] = num[low]; } num[low] = temp; return low; } }
-
题十五:把数组排成最小的数
2019-04-22 10:17:24题目描述 输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 ... -
剑指offer系列之三十一:把数组排成最小的数
2015-12-11 15:39:54题目描述输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。根据结果判断,所谓最小的数字... -
剑指Offer(Java版)第三十七题:输入一个正整数数组,把数组里所有数字拼接起来排成一个数, 打印能拼接出...
2021-03-14 21:41:47/*输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。*/import java.util.*;public class ... -
从包含10个无符号数的字节数组array中选出最小的一个数存于变量MIN中,并将该数以十进制形式显示出来。
2020-05-23 18:31:33从包含10个无符号数的字节数组array中选出最小的一个数存于变量MIN中,并将该数以十进制形式显示出来。 代码 data segment arrey db 0,1,2,4,6,5,7,9,8,3,5 min db 0 data ends code segment assume cs:code,ds:... -
第二十五题:把数组排成最小的数
2018-03-29 11:43:49题目描述输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。解题思路* 解题思路: * 先将... -
数组排成最小的数(牛客网二十)
2018-01-23 19:34:49输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 import java.util.ArrayList; import ... -
剑指Offer三十二:把数组排成最小的数
2020-04-07 22:39:31输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 思路 若是能够对其进行排序先进行处理,... -
7.从包含10个无符号数的字节数组array中选出最小的一个数存于变量MIN中,并将该数以十进制形式显示出来。
2020-05-28 20:25:578.从包含10个无符号数的字节数组array中选出最小的一个数存于变量MIN中,并将该数以十进制形式显示出来。 data segment array db 11h,13h,4h,5h,7h,8h,2h,1h,14h,10h min db ? data ends code segment assume cs... -
第六十九题(旋转数组中的最小元素)
2014-07-08 10:44:4669.旋转数组中的最小元素。 题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个 排好序的数组的一个旋转, 输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}... -
数组之数组中出现次数超过一半的数字
2019-05-20 14:05:51目录 数组 剑指offer ( 一 ):二维数组中的查找 剑指offer ( 六 ):旋转数组的最小数字 ...剑指offer ( 十三 ):调整... 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为... -
剑指Offer(三十二):把数组排成最小的数
2020-03-23 15:13:38输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 示例 1: 输入: [10,2] 输出: ... -
剑指offer(十四):把数组排成最小的数
2019-09-28 23:42:38输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 分析 通过数组的sort方法,如果a+b>b... -
剑指offer三十二之把数组排成最小的数
2017-10-11 22:38:00输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 二、思路 (1)将数组转换成将数组... -
把数组排成最小的数
2016-12-15 18:32:41问题:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,求所有数字中的最小一个. 详细代码如下: int compare(const void* strNumber1, const void* strNumber2); // int型整数用十进制表示最多只有10... -
剑指 Offer -- 把数组排成最小的数(三十二)
2018-09-04 10:10:20输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 代码(已在牛客上 AC) 详见注释. ... -
剑指offer第三十二题:把数组排成最小的数
2018-09-13 20:27:52输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 思路:设计一个排序依据,实现数组内每... -
牛客剑指offer第三十二题(把数组排成最小的数)
2019-09-22 22:17:46输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 解题思路 采用递归思想,传给递归函数一... -
剑指offer第三十二题把数组排成最小的数
2018-04-25 22:37:28题目描述输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。题目分析第一种暴力思路,枚举... -
剑指Offer第三十二题:把数组排成最小的数
2019-04-09 19:49:10输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 思路:实际上不难,就是排序问题,... -
《剑指offer》第四十五题(把数组排成最小的数)
2019-03-13 15:48:00// 面试题45:把数组排成...// 接出的所有数字中最小的一个。例如输入数组{3, 32, 321},则打印出这3个数 // 字能排成的最小数字321323。 #include <iostream> #include <string> #include <...