我不明白這里發生的問題在哪里。輸入是 [1, 2]。輸出必須是2，但我的代碼給出了1。
問題描述：給定一個整數陣列nums，回傳該陣列中第三個不同的最大數。如果第三個最大值不存在，則回傳最大值。
int thirdMax(int *nums, int numsSize) {
int i, j, k, temp;
for (i = 0; i < numsSize; i ) {
for (j = i 1; j < numsSize; j ) {
if (nums[j] < nums[i]) {
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
for (i = 0; i < numsSize; i) {
while (j = i 1 && j < numsSize) {
if (nums[i] = nums[j]) {
for (k = j; k < numsSize - 1; k)
nums[k] = nums[k 1];
--numsSize;
} else
j;
}
}
if (numsSize >= 3)
return nums[numsSize - 3];
else
return nums[0];
}
uj5u.com熱心網友回復：
所以，為了解決這個問題，你對向量進行排序，洗掉重復項，然后回傳第三個最大值（如果存在）。
去重有兩個錯誤：
while(j=i 1 && j<numsSize)
這不符合你的想法。很難猜出你在想什么。但是那里的任務有錯誤的味道。如下圖：
if(nums[i]=nums[j])
??...不，您真的想在這里進行比較。因此，您可以通過以下方式解決此問題：
for (i = 0; i < numsSize; i) {
j = i 1;
while (j < numsSize) {
if (nums[i] == nums[j]) {
for (k = j; k < numsSize - 1; k) {
nums[k] = nums[k 1];
}
--numsSize;
}
else {
j;
}
}
}
另一個錯誤是在結尾部分：
if(numsSize>=3)
return nums[numsSize-3];
else
return nums[0];
}
如果你有兩個不同的值怎么辦？你應該退回第二個。所以這就是它的作業方式（假設一個非空向量，即numsSize>0）：
if (numsSize >= 3) {
return nums[numsSize - 3];
}
else if (numsSize == 2) {
return nums[1];
}
else {
return nums[0];
}
額外的想法
計算復雜性之神在這里尖叫。排序（使用 O(n^2) 操作），然后使用 O(n^2) 方法洗掉重復項真的很浪費！利用相等的值將相鄰的事實。然后我建議制作那個nums常量，而不是修改它。
這是該函式的 O(n) 版本。我很確定這可以寫得更好，但這就是我想出的。
int thirdMax(int *nums, int numsSize)
{
int maxs[3] = { 0 }; // this is just to silence some warnings
int valid[3] = { 0 };
for (int i = 0; i < numsSize; i) {
if (valid[0]) {
if (maxs[0] < nums[i]) {
if (valid[1]) {
if (maxs[1] < nums[i]) {
if (valid[2]) {
if (maxs[2] < nums[i]) { // new max: kick out 0 and move 1 and 2 down
maxs[0] = maxs[1];
maxs[1] = maxs[2];
maxs[2] = nums[i];
}
else if (maxs[2] > nums[i]) { // between 1 and 2: kick out 0 and move 1 down
maxs[0] = maxs[1];
maxs[1] = nums[i];
}
}
else { // new unseen value (three values now)
valid[2] = 1;
maxs[2] = nums[i];
}
}
else if (maxs[1] > nums[i]) { // between 0 and 1
if (valid[2]) { // kick out 0
maxs[0] = nums[i];
}
else { // put this in between
valid[2] = 1;
maxs[2] = maxs[1];
maxs[1] = nums[i];
}
}
}
else { // new unseen value (two values now)
valid[1] = 1;
maxs[1] = nums[i];
}
}
}
else { // no values up to now
valid[0] = 1;
maxs[0] = nums[i];
}
}
if (!valid[2] && valid[1]) {
return maxs[1];
}
return maxs[0];
}
uj5u.com熱心網友回復：
這里
if(nums[i]=nums[j])
您的目的是檢查是否nums[i]相等nums[j]。而不是你已經損壞了你的陣列，因為nums[i]它的值被nums[j]. 但是，即使您解決了這個問題，您的代碼也是多余的，例如，您不需要對陣列進行排序。這就是您可以簡單地實作相同目標的方法：
int thirdMax(int* nums, int numsSize)
{
int index;
//Handling small array's case
if (numsSize <= 2) {
int max = nums[0];
for (index = 1; index < numsSize; index ) {
if (nums[index] > max) max = nums[index];
}
return max;
}
//Initializing
int first;
int second;
int third;
if ((nums[0] >= nums[1]) && (nums[0] >= nums[2])) {
first = nums[0];
if (nums[1] >= nums[2]) {
second = nums[1];
third = nums[2];
} else {
second = nums[2];
third = nums[1];
}
} else if ((nums[1] >= nums[0]) && (nums[1] >= nums[2])){
first = nums[1];
if (nums[0] >= nums[1]) {
second = nums[0];
third = nums[1];
} else {
second = nums[1];
third = nums[0];
}
} else {
first = nums[2];
if (nums[0] >= nums[1]) {
second = nums[0];
third = nums[1];
} else {
second = nums[1];
third = nums[2];
}
}
//Looping
int distinct1 = nums[0];
int distinct2 = nums[0];
int distinct3 = nums[0];
for (index = 3; index < numsSize; index ) {
if ((distinct1 == distinct2) && (nums[index] != distinct1)) {
distinct2 = nums[index];
} else if ((distinct1 != distinct2) && (distinct2 == distinct3) && (nums[index] != distinct1) && (nums[index] != distinct2)) {
distinct3 = nums[index];
}
if (nums[index] > third) {
third = nums[index];
if (third > second) {
int aux = second;
second = third;
third = aux;
if (second > first) {
int aux = first;
first = second;
second = aux;
}
}
}
}
return (distinct2 == distinct3) ? third : first;
}
uj5u.com熱心網友回復：
這是另一種不修改陣列并在O(n)時間內運行的替代方法。它使用 3 次通行證：
- find
max，陣列的最大值，假設長度至少為 1 max2找到小于的最大值（max如果有）- 找到最大值，如果有則
max3小于max2
如果第二次或第三次沒有找到新的最大值，max請按照問題中的說明回傳。
int third_max(const int *nums, int len) {
int max = nums[0];
for (int i = 1; i < len; i ) {
if (max < nums[i])
max = nums[i];
}
int max2 = 0, has_max2 = 0;
for (int i = 0; i < len; i ) {
if (nums[i] < max && (!has_max2 || max2 < nums[i]))
max2 = nums[i];
}
if (!has_max2)
return max;
int max3 = 0, has_max3 = 0;
for (int i = 0; i < len; i ) {
if (nums[i] < max2 && (!has_max3 || max3 < nums[i]))
max3 = nums[i];
}
if (!has_max3)
return max; // If the third maximum does not exist, return the maximum number
else
return max3; // return the third maximum
}
uj5u.com熱心網友回復：
正如在之前的答案中已經指出的那樣，使用賦值而不是比較會出錯。
我會在前面的答案中補充一點，（取決于用例）您不需要撰寫自己的排序函式。有qsort。
請參閱： 執行排序的 C 庫函式
你可以這樣做：
#include <stdlib.h>
#include <string.h>
int compare_int(const void *a, const void *b)
{
const int _a = *((const int*)a);
const int _b = *((const int*)b);
return (_a > _b) - (_a < _b);
}
/* This method returns the nth largest integer in your array. */
int nthmax(const int* arr, const size_t size, const unsigned int n)
{
if (size <= 0) return arr[0];
int* sorted_arr = malloc(size * sizeof(*arr));
int* sorted_set_arr = malloc(size * sizeof(*arr));
memcpy(sorted_arr, arr, size * sizeof(*arr));
qsort(((void*)sorted_arr), size, sizeof *arr, compare_int);
size_t new_size = 1;
sorted_set_arr[0] = sorted_arr[0];
for (unsigned int i = 1; i < size; i)
{
if (sorted_set_arr[new_size - 1] != sorted_arr[i])
{
sorted_set_arr[new_size ] = sorted_arr[i];
}
}
size_t nselect = n >= new_size ? new_size - 1 : n;
nselect = new_size - nselect - 1;
const int nthmaxed = sorted_set_arr[nselect];
free(sorted_arr);
free(sorted_set_arr);
return nthmaxed;
}
這樣，您的原始陣列保持原樣，但是這種方法可能會更難記憶。
另外：我并沒有真正處理空大小的陣列，所以使用它需要您自擔風險。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/487158.html
上一篇：為什么在使用%s和malloc時會有額外的字符？[復制]
下一篇：找出五個整數的中間數