找出给定数组中的最大和最小元素
问题描述：
给你一个数字数组。你需要在数组中找到最小和最大的数。
思路：
- 定义两个变量max，min，用来存放最大和最小元素
- 遍历数组
- 如果当前元素大于max，则将当前元素赋值给max
- 如果当前元素小于min，则将当前元素赋值给min
- 最后max和min则是最大和最小的元素
代码实现：
public class FindLargestSmallestNumberMain {
public static void main(String[] args) {
int arr[] = new int[]{12,56,76,89,100,343,21,234};
//将第一个元素赋值给
int min = arr[0];
int max = arr[0];
for(int i=1; i< arr.length; i++)
{
if(arr[i] > max)
max = arr[i];
else if (arr[i] < min)
min = arr[i];
}
System.out.println("Smallest Number is : " + min);
System.out.println("max Number is : " + max);
}
}
复制代码
查找数组中缺少的数字
问题描述：
给定一个包含1到n的整数递增数组，但数组中从1到n的一个数字缺失了。你需要提供一个最佳的解决方案来找到丢失的数字。数字不会在数组中重复。
例如：
int[] arr1={7,5,6,1,4,2};
Missing number : 3
int[] arr2={5,3,1,2};
Missing number : 4
复制代码思路：
- 因为数组中元素是递增的，所以可以使用公式n=n*(n+1)/2求n个数的和
- 计算出给定数组中元素的和
- 使用n个数的和减去数组中元素的和结果便是缺少的数字
代码实现：
public class MissingNumberMain {
public static void main(String[] args) {
int[] arr1={7,5,6,1,4,2};
System.out.println("Missing number from array arr1: "+missingNumber(arr1));
int[] arr2={5,3,1,2};
System.out.println("Missing number from array arr2: "+missingNumber(arr2));
}
public static int missingNumber(int[] arr)
{
int n=arr.length+1;
int sum=n*(n+1)/2;
int restSum=0;
for (int i = 0; i < arr.length; i++) {
restSum+=arr[i];
}
int missingNumber=sum-restSum;
return missingNumber;
}
}
复制代码从旋转的有序数组中查找元素
问题描述：
给定一个排序和旋转的数组，如下所示:
int arr[]={16,19,21,25,3,5,8,10};
复制代码该数组是从一个有序数组arr[]={3,5,8,10,16,19,21,25}旋转后所得。
要求在在O(log n)时间复杂度的数组中搜索到一个指定元素。
思路：
- 如果直接遍历数组，则时间复杂度为O(n)，不符合题目要求；
- 因为数组是由有序数组旋转所得，所以在某个下标的之前和之后是有序的；
- 然后按照二分法查找。
算法逻辑：
- 计算出中位下标mid=(low+high)/2；
- 如果arr[mid]等于要查找的数字则返回；
- 如果[low...mid]是有序的；
- 如果要查找的数字在[low...mid]，则high=mid-1;
- 如果要查找的数字不在[low...mid]，则low=mid+1;
- 如果[mid...high]是有序的；
- 如果要查找的数字在[mid...high]，则low=mid+1;
- 如果要查找的数字不在[mid...high]，则high=mid-1;
代码实现：
public class SearchElementSortedAndRotatedArrayMain {
public static void main(String[] args) {
int arr[] = {16, 19, 21, 25, 3, 5, 8, 10};
System.out.println("Index of element 5 : " + findElementRotatedSortedArray(arr, 0, arr.length - 1, 5));
}
public static int findElementRotatedSortedArray(int[] arr, int low, int high, int number) {
int mid;
while (low <= high) {
mid = low + ((high - low) / 2);
if (arr[mid] == number) {
return mid;
}
if (arr[mid] <= arr[high]) {
// 右边部分是有序的
if (number > arr[mid] && number <= arr[high]) {
low = mid + 1;
} else {
high = mid - 1;
}
} else {
// 左边部分是有序的
if (arr[low] <= number && number < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
return -1;
}
}找到有序旋转数组中的最小元素
问题描述：
有序旋转数组定义同上一题，例如：
int arr[]={16,19,21,25,3,5,8,10};同样要求时间复杂度为O(log n)。
思路：
与上题类似，因数组可以拆分为前后两个有序数组，可以通过二分查找法的变体来完成；
- 计算出中位下标mid=(low+high)/2；
- 如果[mid...high]是有序的；
- 最小值在右边，high=mid;
- 否则最小值在左边，low= mid+1;
代码实现：
public class MinimumElementSortedAndRotatedArrayMain {
public static void main(String[] args) {
int arr[] = {16, 19, 21, 25, 3, 5, 8, 10};
System.out.println("Minimum element in the array : " + findMinimumElementRotatedSortedArray(arr, 0, arr.length - 1));
}
public static int findMinimumElementRotatedSortedArray(int[] arr, int low, int high) {
int mid;
while (low < high) {
mid = low + ((high - low) / 2);
if (arr[mid] < arr[high]) {
high = mid;
} else {
low = mid+1;
}
}
return arr[low];
}
}查找数组中第二大的与元素
问题描述：
给定一个旋转有序数组，如下所示：
int[] arr1={7,5,6,1,4,2};
复制代码找出第二大的元素：6
思路：
可以对数组排序，然后返回数组中的倒数第二个元素，时间复杂度为O(nlogn)。
- 定义最大值highest 和第二大值变量secondHighest
- 对数组进行遍历
- 如果当前元素大于最大值
- 将highest赋值给secondHighest
- 将当前元素赋值给highest
- 否则，如果当前元素大于secondHighest
- 将当前元素赋值给secondHighest
代码实现：
public class FindSecondLargestMain {
public static void main(String args[]) {
int[] arr1 = {7, 5, 6, 1, 4, 2};
int secondHighest = findSecondLargestNumberInTheArray(arr1);
System.out.println("Second largest element in the array : " + secondHighest);
}
public static int findSecondLargestNumberInTheArray(int array[]) {
int highest = Integer.MIN_VALUE;
int secondHighest = Integer.MIN_VALUE;
// 遍历数组
for (int i = 0; i < array.length; i++) {
// 如果当前值大于最大值
if (array[i] > highest) {
// 最大值赋值给第二大值
secondHighest = highest;
// 当前值赋值给最大值
highest = array[i];
} else if (array[i] > secondHighest && array[i] != highest)
// 将当前值赋值给第二大值
secondHighest = array[i];
}
return secondHighest;
}
}找出数组中出现奇数次的数
题目描述：
给定一个整数数组， 只有一个数字出现奇数次，其他数字都出现偶数次。 你需要找到奇数次出现的数字。 需要用O(n)时间复杂度和O(1)空间复杂度来解决它。
思路1：
暴力解法：使用两层循环，记录每个元素出现的次数，这种方法的时间复杂度为O(n^2)，不是最优解。
思路2：
使用Hash,将数字作为key，出现的次数作为value，每当key重复时，value+1，这种解法的时间复杂度为O(n)，但是空间复杂度也为O(n)，不符合要求。
代码实现：
int getOddTimesElementHashing(int ar[]) {
int i;
HashMap<Integer, Integer> elements = new HashMap<Integer, Integer>();
for (i = 0; i < ar.length; i++) {
int element = ar[i];
if (elements.get(element) == null) {
elements.put(element, 1);
} else{
elements.put(element, elements.get(element) + 1);
}
}
for (Entry<Integer, Integer> entry : elements.entrySet()) {
if (entry.getValue() % 2 == 1) {
return entry.getKey();
}
}
return -1;
}思路3：
基于位运算异或操作。
异或运算：相同为0，不同为1。如a=1001,b=1010，则a^b=0010，a^a=0000。
按照题目描述，数组中只有1个数字出现奇数次，其他数字都是偶数次，则将所有数字异或运算后的结果就是出现奇数次的数字。
代码实现：
int getOddTimesElement(int arr[]) {
int i;
int result = 0;
for (i = 0; i < arr.length; i++) {
result = result ^ arr[i];
}
return result;
}该解法的时间复杂度为O(n)；因为只使用了一个变量result，所以空间复杂度为O(1)。
计算火车站需要的最少站台数
题目描述：
给定两个数组，分别对应火车站车辆到达的时间和出站的时间，计算出火车站最少需要几个站台。
// 到达时刻表
arrival[] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00}
// 出站时刻表
departure[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00}
// 最少需要的站台数 = 4思路1：
遍历两个数组，检查每个到达和出站的时间间隔有多少重叠。
这种方式的时间复杂度为O(n^2)，不是最优解。
思路2：
使用归并排序的逻辑。
- 对到达和出发的数组进行排序；
- 因为到达和出站数量一样，则从两个数组中取出相同位置的元素比较时间大小；
- 如果到达时间早，则站台数加1；
- 如果出站时间早，则站台数减1；
- 在这个过程中记录最大的站台数；
- 最后返回最大站台数的值。
这种算法的时间复杂度为O(n*log n)。
代码实现：
public class TrainPlatformMain {
public static void main(String args[]) {
// arr[] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00}
// dep[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00}
int arr[] = {100, 140, 150, 200, 215, 400};
int dep[] = {110, 300, 210, 230, 315, 600};
System.out.println("最少需要的站台数 =" + findPlatformsRequiredForStation(arr, dep, arr.length));
}
static int findPlatformsRequiredForStation(int arr[], int dep[], int n) {
int platform_needed = 0, maxPlatforms = 0;
Arrays.sort(arr);
Arrays.sort(dep);
int i = 0, j = 0;
// 类似归并排序中的归并操作
while (i < n && j < n) {
if (arr[i] < dep[j]) {
platform_needed++;
i++;
if (platform_needed > maxPlatforms)
maxPlatforms = platform_needed;
} else {
platform_needed--;
j++;
}
}
return maxPlatforms;
}
}数组中最两数之和最接近0的两个数
题目描述：
一个数组中有一系列的正数和负数，找出数组中两数之和最接近0的两个数。
例如：
array[]={1,3,-5,7,8,20,-40,6};
// 和最接近0的两个数是 : -5 and 6思路1：
暴力解法：将所有数字两两求和，如果和的绝对值更小，则赋值记录两数的值。
这种方法的时间复杂度为O(n^2)，不是最优解。
代码实现：
public static void findPairWithMinSumBruteForce(int arr[]) {
if (arr.length < 2)
return;
// 预设前两个数的和最接近于0
int minimumSum = arr[0] + arr[1];
int pair1stIndex = 0;
int pair2ndIndex = 1;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
int tempSum = arr[i] + arr[j];
if (Math.abs(tempSum) < Math.abs(minimumSum)) {
pair1stIndex = i;
pair2ndIndex = j;
minimumSum = tempSum;
}
}
}
System.out.println(" 和最接近0的两个数是 : " + arr[pair1stIndex] + " " + arr[pair2ndIndex]);
}思路2：
- 对数组进行排序；
- 定义两个索引对应数组的开始位置l=0,一个在结束位置r=n-1;
- 按照l<r的条件循环
- 计算arr[l]+arr[r]的和sum
- 如果abs(sum)<abs(minSum)，将l和r记录在最小的两个数组元素变量上；
- 如果sum>0，则sum要更接近0需要将大值往小移动，r--;
- 如果sum<0，则sum要更接近0需要将小值往大移动，l++。
代码实现：
public static void findPairWithMinSum(int arr[]) {
Arrays.sort(arr);
int sum = 0;
int minimumSum = Integer.MAX_VALUE;
int n = arr.length;
// left and right index variables
int l = 0, r = n - 1;
int minLeft = l, minRight = n - 1;
while (l < r) {
sum = arr[l] + arr[r];
// 如果abs(sum)<abs(minSum)，将l和r记录在最小的两个数组元素变量上;
if (Math.abs(sum) < Math.abs(minimumSum)) {
minimumSum = sum;
minLeft = l;
minRight = r;
}
if (sum < 0)
l++;
else
r--;
}
System.out.println(" 和最接近0的两个数是 : " + arr[minLeft] + " " + arr[minRight]);
}该算法的时间复杂度为O(NLogN)。
数组中最两数之和最接近X的两个数
该问题为上一题的进阶版，找出两数之和最接近X的数。
思路1：
暴力解法：两层循环，求和与最接近的数进行比较，如果更小则记录对应数字，时间复杂度为O(n^2)，不是最优解。
思路2：
与上一题的区别在于该问题要对求和结果比较的值是指定的X，不是0，不能直接使用abs()函数的结果进行比较；那该如何处理呢？
可以通过将abs()结果减去X，则对应该问题的解法。
- 对数组进行排序；
- 定义两个索引对应数组的开始位置l=0,一个在结束位置r=n-1;
- 按照l<r的条件循环
- 计算arr[l]+arr[r]-x的结果diff
- 如果abs(diff)<minDiff，将l和r记录在最小的两个数组元素变量上；
- 如果sum>x，则sum要更接近x需要将大值往小移动，r--;
- 如果sum<x，则sum要更接近x需要将小值往大移动，l++。
代码实现：
public static void findPairWithClosestToX(int arr[], int X) {
Arrays.sort(arr);
int minimumDiff = Integer.MAX_VALUE;
int n = arr.length;
int l = 0, r = n - 1;
int minLeft = l, minRight = n - 1;
while (l < r) {
int currentDiff = Math.abs(arr[l] + arr[r] - X);
// 如果abs(diff)<minDiff，将l和r记录在最小的两个数组元素变量上
if (currentDiff < minimumDiff) {
minimumDiff = currentDiff;
minLeft = l;
minRight = r;
}
if (arr[l] + arr[r] < X)
l++;
else
r--;
}
System.out.println(" 和最接近X的两个数是 : " + arr[minLeft] + " " + arr[minRight]);
}数组中两数之和等于X的所有组合
题目描述：
给定一个数组和一个指定数字，查找出数组中所有两数之和等于指定数字的组合。
思路1：
两层循环暴力解法，时间复杂度低，不是最优解。
代码实现：
public static void findPairsWithSumEqualsToXBruteForce(int arr[], int X) {
if (arr.length < 2)
return;
System.out.println("暴力破解两数之和等于X的组合: ");
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
int tempSum = arr[i] + arr[j];
if (tempSum == X) {
System.out.println(arr[i] + " " + arr[j]);
}
}
}
}思路2：
对数组进行排序；
从数组的两端进行遍历，直到相遇，使用l代表左边，r代表右边；
如果arr[l]+arr[r]=X，则符合条件，打印结果，l--,r--;
如果arr[l]+arr[r]>X，则表示结果偏大，需要将大值降低，r--;
如果arr[l]+arr[r]<X，则表示结果偏小，需要将小值升高，l++;
代码实现：
public static void findPairsEqualsToX(int arr[], int X) {
int n = arr.length;
if (n < 2)
return;
Arrays.sort(arr);
System.out.println("两数之和等于X的组合: ");
int l = 0, r = n - 1;
while (l < r) {
int currentSum = arr[l] + arr[r];
if (currentSum == X) {
System.out.println(arr[l] + " " + arr[r]);
l++;
r--;
} else if (arr[l] + arr[r] < X)
l++;
else
r--;
}
}该解法时间复杂度为：O(NLogN)。
思路3：
- 使用HashMap，将数组元素的值作为key，下标作为value放入map中；
- 遍历数组；
- 如果X-arr[i]在HashMap中存在，则从Map中取出结果，代表符合条件。
代码实现：
public static void findPairsEqualsToXUsingHashing(int arr[], int X) {
HashMap<Integer, Integer> elementIndexMap = new HashMap<>();
System.out.println("两数之和等于X的组合: ");
for (int i = 0; i < arr.length; i++) {
elementIndexMap.put(arr[i], i);
}
for (int i = 0; i < arr.length; i++) {
if (elementIndexMap.get(X - arr[i]) != null && elementIndexMap.get(X - arr[i]) != i) //
{
System.out.println(arr[i] + " " + (X - arr[i]));
}
}
}
相关推荐
-
c语言编程总有一个错误（c语言写程序为什么都是错误）
我想你要表达的是，编绎时，没显示出错，但就是结果错了。要细致地找原因。根据我以往的经验，原因有以下几点。1，内存没有释放。用new，malloc等分配内存，而在结束时来释放，频繁调用，系统崩溃。或者根本没使用ne...
-
php7字符串转数组（php7把字符串转换成数组）
php7字符串转数组方法：1、用str_split()，语法“str_split(str,length)”；2、用explode()，语法“explode(separator,str,limit)”；3、用强制转换，语法“(array)string”。 php7字符串转数组（php7把字符串转换成数组）...
-
JS Array 中各类函数如何使用（js数组常用的方法及用法）
对于web开发过程中的JS对象 Array ，我们真的充分使用了么？是不是理解了Array的全部？能够在合适的地点调用合适的函数，使用合适的属性？ 接下来我们一起走进JS原生对象Array的世界中. Array如何创建 1.空数组 var ...
-
new array.at()方法的用法
现在有一个新的数组方法：array.at()，与普通方括号访问语法的主要区别是对负索引的支持。 让我们看看以下数组： [] 和 at() 会做同样的事情： 虽然 legumes[-1] 最终会返回 undefined，但 legumes.at(-1) 将返回&qu...
-
js中array对象的常用方法(js array的方法)
JS是唯一几乎全面支持函数式编程的流行语言，而函数编程的起点是处理数组。因此，我们首先来盘点 array 数组的5类22种方法。 一、数组变形 Transform (函数范式的纯函数） 首先列出对数组变形操作的没有side-effects...
-
VBA数组函数Array（vba数组函数的使用方法）
【分享成果，随喜正能量】承担生活的深沉，品味辛苦的味道，看淡世间的颠倒与世相，活出生活的才情和智慧，那些所有复杂变得平淡，纠结变得朴素，都是生活的醒悟，更是人生的灵犀一点，佛门有句话，叫做道不远人，生...
